CF643F Bears and Juice 题解
Visits: 375
题意
- 有 $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;
}