CF643F Bears and Juice 题解

CF643F Bears and Juice

题意

有 $n$ 只熊和 $p$ 张床，还有若干个无限大的酒桶（至少一个），其中恰好只有一个酒桶里装着酒，其它酒桶里都装着果汁。
熊一开始不知道哪桶里面是酒，于是进行了一次挑战，目标是找到哪桶里面是酒。
每天，每只还醒着的熊会选择一个酒桶的子集（可以为空集），并且喝下选择的酒桶中的一小杯饮料。
如果一只熊喝到了酒，它会上床睡觉一直到挑战结束。但一张床只能容纳一只熊，如果有熊没有床睡觉，则挑战失败。
如果 $i$ 天后至少还剩一只熊没睡觉，且能根据前面的线索推理出哪桶里面是酒，则挑战成功。
请你求出对于 $i \in [1,q]$ ，在可以确保挑战成功的情况下，最多有多少个酒桶。
设对于 $i$ 的答案为 $R_i$ ，你需要求出 $\operatorname{xor}_{i=1}^q ((i \times R_i) \bmod 2^{32})$ 。
$n \le 10^9$ ， $p \le 130$ ， $q \le 2 \times 10^6$ 。

题解

这道题需要从「信息」的角度考虑。什么叫从「信息」的角度呢？

举个例子，我们都知道 $\text{sort}$ 的时间复杂度为 $\mathcal O(n \log n)$ ，这是基于比较的排序的时间复杂度下界吗？

显然一共有 $n!$ 中不同的方案，我们排序的目的就是区分这 $n!$ 个方案。

每次比较可以得到的全部「信息」为两个元素的相对顺序，根据这个「信息」，有一半的方案会被区分掉，还剩下一半的方案。

那么 $k$ 次比较还剩下的方案数就应该为 $\frac{n!}{2^k}$ ，我们最终要求只剩下一个方案，即 $\frac{n!}{2^k} \le 1$ ， $k = \mathcal O(\log (n!)) = \mathcal O(n \log n)$ 。

回到本题，我们能够得到的全部「信息」为：

一只熊最终有没有睡觉。
如果它睡觉了，是在第几天睡的。

根据这些「信息」，当天数为 $i$ 时，我们可以区分的方案数的上界为： $R_i = \sum_{j=0}^{\min(p,n-1)}\binom{n}{j} \times i^j$ 解释一下这个公式：

枚举睡觉的熊的个数 $j$ ，由于一共只有 $p$ 张床，而不能所有熊都睡觉，因此睡觉的熊的个数最多为 $\min(p,n-1)$ 。
$n$ 只熊里面选 $j$ 个睡觉，方案数为 $\binom nj$ 。
每只睡觉的熊可以在 $i$ 天中选择一天睡觉， $j$ 只熊的方案数为 $i^j$ 。

那这个上界是否一定能达到呢？

我们将所有的方案排成一排，第 $k$ 个方案对应第 $k$ 个酒桶里面有酒。

如果在第 $k$ 个方案中，某一只熊最终没有睡觉，则自始至终不让这只熊喝第 $k$ 桶；否则，让它在睡觉的那一天喝第 $k$ 桶。

这样，我们就构造出来了一种达到上界的情况。

于是，我们现在要计算的式子为： $\operatorname{xor}_ {i=1}^q \left(\left(i \times \left(\sum_ {j=0}^{\min(p,n-1)}\binom{n}{j} \times i^j\right)\right) \bmod 2^{32}\right)$ 直接暴力枚举 $i,j$ 计算时间复杂度为 $\mathcal O(pq)$ ，可以接受。

但问题在于这个组合数 $\binom nj$ 如何计算。

注意到 $p$ 非常小，考虑预处理出 $\binom{n}{0\cdots\min(p,n-1)}$ 。

对于 $\binom{n}{j}$ ，我们将其写成 $\frac{n \times (n - 1) \times \cdots \times (n - j + 1)}{j!}$ ，然后暴力枚举上下的每一项，除以它们的 $\gcd$ 进行约分。

这样到最后，分母一定会被约为 $1$ ，时间复杂度为 $\mathcal O(p^3 \log p)$ 。

总时间复杂度 $\mathcal O(p^3 \log p + pq)$ 。

代码

const ui N = 137;
ui n, p, q, ans[N], Ans;

inline ui calc(ui j) {
	vector<ui> a, b;
	for (ui i = 1; i <= j; i++)
		a.pb(n + 1 - i), b.pb(i);
	for (ui &x : a)
		for (ui & y : b) {
			ui d = __gcd(x, y);
			x /= d, y /= d;
		}
	ui ans = 1;
	for (ui x : a) ans *= x;
	return ans;
}

int main() {
	rd(n), rd(p), rd(q), p = min(p, n - 1);
	for (ui j = 0; j <= p; j++) ans[j] = calc(j);
	for (ui i = 1; i <= q; i++) {
		ui now = 0;
		for (ui j = 0, k = 1; j <= p; j++, k *= i)
			now += ans[j] * k;
		Ans ^= now * i;
	}
	print(Ans);
	return 0;
}

题意

题解

代码

评论