CF643F Bears and Juice 题解

作者: xht37 分类: 题解 发布时间: 2020-03-10 14:00

点击数:131

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
$$
解释一下这个公式:

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

代码

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注