题解 CF643F 【Bears and Juice】

xht · 2020-03-10 14:07:34 · 题解

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})。

题解

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

举个例子，我们都知道 \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)。
每只睡觉的熊可以在 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;
}