题解 CF643F 【Bears and Juice】

> [CF643F Bears and Juice](https://codeforces.com/contest/643/problem/F) ## 题意 - 有 $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 $$ 解释一下这个公式： 1. 枚举睡觉的熊的个数 $j$，由于一共只有 $p$ 张床，而不能所有熊都睡觉，因此睡觉的熊的个数最多为 $\min(p,n-1)$。 2. $n$ 只熊里面选 $j$ 个睡觉，方案数为 $\binom nj$。 3. 每只睡觉的熊可以在 $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)$。 ## 代码 ```cpp 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; } ```