CF643F Bears and Juice

有趣的信息量分析 + 组合数学题目。

题意：有一些个酒桶，有一个是酒，另外的都是果汁，有 $n$ 只熊玩游戏，每天可以选择一些酒桶集合（可以为空），倒出一杯喝掉，如果喝到了酒就会睡觉到游戏结束，并且不能超过 $p$ 只熊在睡觉，否则判为失败。如果至少有一只熊没有睡觉，并且他能判断哪一个是酒，就算游戏胜利。问给 $t$ 天时间，这些熊最多能辨别多少个酒桶。你需要给出 $t\in [1, q]$ 的答案，并将 $\oplus i\times ans_i$ 输出，对 $2 ^ {32}$ 取模。$n\leq 10 ^ 9$，$p\leq 130$，$q\leq 2\times 10 ^ 6$。

考虑最大的信息量，$n$ 只熊有 $i$ 只睡着了，有 $\binom ni$ 种情况；这 $i$ 只熊可以在 $[1, t]$ 的时间内任意一天开始睡觉，得到的信息量为 $t ^ i$。那么就可以得到：

$$ans_t = \sum_{i = 0} ^ {\min\{n - 1, p\}} \binom ni t ^ i$$

这个为什么是对的呢？首先容易发现这是上界，因为我们最多只能得到这么多的信息，能区分的也就只有这么多了。

下面我们需要干的事情就是构造一种方案使得正好能区分这么多的信息量。考虑对所有情况编一个号，它对应着选出了哪些熊睡觉，还有睡觉的那些熊多久开始睡觉。没有被选中的始终不会碰这一个酒桶；被选中的熊会在自己对应的天数选中这个酒桶。容易发现不同的酒桶其实是独立的，因为我可以选择任意多的酒桶。

那么我们就得到了构造，也就得到了答案。下面考虑如何计算。

其实 $t ^ i$ 这一部分是简单的，可以在 $O(pq)$ 的时间内做完，可以承受。计算 $\displaystyle \binom ni$ 可以拆成下降幂除以阶乘的形式，然后暴力枚举两个数并约分。注意到这个是整数，所以一定是合法的。求解单个的复杂度为 $O(p ^ 2\log n)$，可以接受。

总时间复杂度 $O(p ^ 3\log n + pq)$，可以通过。

uint C(uint n, uint m)
{
	std::vector<uint> a(m), b(m);
	for (uint i = 0; i < m; ++ i) a[i] = n - i;
	for (uint j = 0; j < m; ++ j) b[j] = j + 1;
	for (uint &x : a)
		for (uint &y : b) {
			uint G = Gcd(x, y);
			x /= G, y /= G;
		}
	uint res = 1;
	for (uint &x : a) res *= x;
	return res;
}
 
int main()
{
	std::cin >> n >> p >> T;
	uint ed = std::min(n - 1, p);
	std::vector<uint> bn(ed + 1);
	for (uint i = 0; i <= ed; ++ i) bn[i] = C(n, i);
	uint res = 0;
	for (uint t = 1; t <= T; ++ t)
	{
		uint ans = 0, cur = 1;
		for (uint i = 0; i <= ed; ++ i, cur *= t) ans += cur * bn[i];
		res ^= ans * t;
	}
	std::cout << res << '\n';
	return 0;
}