CF643F Bears and Juice

【题解】CF643F Bears and Juice

模拟赛的 T2，一车人过，感觉十分震撼。

题目描述：

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

题目分析：

感觉这个题好高妙啊。
考虑通过【信息】的角度理解这个问题，我们知道的信息其实只有：熊睡没睡，如果睡了则在哪一天睡的。
以 $n=3，p=2，k=1$ 这个样例为例，我们可以得到如下七种信息：
设 $(i,j)$ 表示熊 $i$ 在第 $j$ 天睡了。

1. 熊都没有睡
2. $(1,1)$
3. $(1,1)(2,1)$
4. $(1,1)(3,1)$
5. $(2,1)(3,1)$
6. $(2,1)$
7. $(3,1)$

如果要使得确定的数量仅可能多，一个想法就是让每一种信息对应一种酒的放置方案，而样例也恰好是如此。
有这种构造：如果在第 $i$ 条信息中，熊 $j$ 在第 $k$ 天睡了，则让熊 $j$ 在第 $k$ 天喝第 $i$ 个酒桶。
这样可以显然发现，如果恰好满足第 $i$ 条信息的情况，则酒必然是在第 $i$ 个酒桶中。
以上述为例，则三个熊喝酒桶的情况如下：
设 $(i,j)$ 表示第 $i$ 天喝了酒 $j$。

1. $(1,2)(1,3)(1,4)$
2. $(1,3)(1,5)(1,6)$
3. $(1,4)(1,5)(1,7)$

所以也就是说，信息的数量与酒桶的最多数量是相等的，假设有 $d$ 天，则显然：

$$R_d = \sum_{i=0}^{\min(p,n-1)} \binom{n}{i} d^i$$

其实就是枚举哪头熊在哪一天睡/不睡的方案数。
这里就是枚举了 $i$ 头熊睡了，每头熊都可以在 $d$ 天其中之一睡觉，$i$ 头熊可以是 $n$ 个里面的任意 $i$ 头。
所以我们的答案就很显然了：

$$\text{xor}_{i=1}^q (i \times \sum_{j=0}^{\min(p,n-1)} \binom{n}{j} i^j \mod 2^{32})$$

直接暴力枚举复杂度 $O(pq)$ 可以通过。
但是注意到这个组合数就很难算，因为组合数需要计算 $(j!)^{-1} \mod 2^{32}$，而这个东西可能并不存在逆元。
有以下三种解决这个问题的方法：

方法一：
考虑：

$$\binom{n}{i} = \frac{n^{\underline{i}}}{i!} = \frac{n \times (n-1) \times \cdots \times (n-i+1)}{1 \times 2 \times \cdots \times i}$$

而组合数一定是一个整数，也就是说分子一定是分母的倍数，就可以考虑用分子的每一个数与分母的每一个数，求它们的 $\gcd$，然后上下同时除以这个 $\gcd$，最后一定会将分母约成 $1$，就不需要逆元这个问题了。

方法二：
考虑：

$$\binom{n}{i} = \frac{A \times 2^{a}}{B \times 2^b}$$

也就是把 $2$ 的幂提出来，因为分子一定是分母的倍数，即 $a > b$，所以可以直接将 $2$ 的幂丢出去，即求：

$$\frac{A}{B} \times 2^{a-b}$$

因为我们将 $2$ 的幂全部提出来了，即 $\gcd(B,2^{32}) = 1$，所以就可以求得 $B$ 的逆元了，使用 exgcd 求解即可。

方法三：
exLucas，但是太难写了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
unsigned int C[N],a[N],b[N];
int n,p,q;
unsigned int get(int x){
	for(int i=1; i<=x; i++){
		a[i] = n - i + 1;
		b[i] = i;
	}
	for(int i=1; i<=x; i++){
		for(int j=1; j<=x; j++){
			int gc = __gcd(a[i],b[j]);
			a[i] /= gc,b[j] /= gc;
		}
	}
	unsigned int ans = 1;
	for(int i=1; i<=x; i++)	ans = ans * a[i];
	return ans;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d%d",&n,&p,&q);
	for(int i=0; i<=min(p,n-1); i++)	C[i] = get(i);
//	for(int i=0; i<=min(p,n-1); i++)	printf("%u\n",C[i]);
	long long ans = 0;
	for(int i=1; i<=q; i++){
		unsigned int tmp = 0;
		unsigned int k = i;
		for(int j=0; j<=min(p,n-1); j++,k=(unsigned int)k*i){
			tmp = tmp + C[j] * k;
		}
		ans = ans ^ tmp;
	}
	printf("%lld\n",ans);
	return 0;
}