【Codeforces 643F】Bears and Juice
组合数学。
题目大意：
有 $n$ 只熊，$p$ 张床，还有一些桶，其中有且仅有一个桶里装着酒。熊初始都醒着。每张床只能容纳一只熊。
有 $k$ 天，每天每只醒着的熊都可以选择一些桶，喝里面的东西（可以选择什么都不喝）。如果一只熊喝到了酒，那么它会去找一张床睡觉，并且在之后几天里都不醒来。
如果有一只熊要睡觉时没有空着的床，或者 $k$ 天结束后没有醒着的熊，或者 $k$ 天结束后熊不能通过已知信息判断酒在哪个桶里，则挑战失败。如果能够判断，则挑战成功。
现在要对于 $i\in[1,k]$，求出 $R_i$ 满足有 $R_i$ 个桶的时候熊一定能挑战成功且有 $R_i+1$ 个桶的时候熊不能保证挑战成功。
答案对 $2^{32}$ 取模。
题解：
由于最后要有醒着的熊，所以最多有 $\min(p,n-1)$ 头熊睡觉。所以可以直接令 $p=\min(p,n-1)$。
对于一个桶，最多只能有不超过 $p$ 只熊喝过它，否则万一它是酒，床就不够了。
对于两个桶，如果喝过它的熊是一样的，且每个熊喝它们的天数是同一天，那么就无法判断这两个桶哪个是酒了。
如果没有两个桶的熊及对应天数相同，那么我们可以通过 $k$ 天后有哪些熊去睡觉了，每只熊是第几天睡觉的，从而唯一确定哪个是酒。
这样的不同信息有 $\sum\limits_{i=0}^p\binom{n}{i} k^i$ 种。其中 $k$ 为当前计算的天数。
这是一个上界。并且这个上界可以达到。
我们不会安排一只熊喝一个桶多次。因为如果它是酒，则第一次喝就会去睡觉，否则永远不会睡觉。因此我们可以对熊喝每个桶的时间唯一确定。
考虑求这个答案：
由于 $p\leq 130$，$q\leq 2\times 10^6$，因此我们对 $q$ 天，每次 $O(p)$ 暴力算出 $R_i$，$O(pq)$ 的复杂度可以接受。
考虑如何求模 $2^{32}$ 意义下的组合数。
我们可以从 $\binom{n}{i-1}$ 递推到 $\binom{n}{i}$，需要乘 $n-i+1$ 并除以 $i$。由于模 $2^{32}$ 意义下偶数不存在逆元，所以要先同时消去因子 $2$，然后奇数的逆元可以使用 exgcd 来求。这个可以预处理。
于是时间复杂度 $O(pq)$。
中间过程用 unsigned 会爆（除以 $2$ 时最高位溢出的位会被忽略），可以用 long long 存下中间结果。
Code：
#include<iostream>
using namespace std;
typedef unsigned uint;
typedef long long LL;
int n,p,q;
uint iv[132];
void exgcd(LL a,LL b,LL&x,LL&y){
if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=a/b*x;
}
int main(){
scanf("%d%d%d",&n,&p,&q);
if(p>n-1)p=n-1;
for(int i=1;i<=p;++i)
if(i&1){
LL x,y;
exgcd(1LL<<32,i,x,y);
iv[i]=(uint)y;
}
uint ans=0;
for(int i=1;i<=q;++i){
unsigned long long s=0,C=1,q_=1;
for(int t=0;t<=p;++t){
s+=C*q_;
C*=n-t;
int y=t+1,z=__builtin_ctz(y);
y>>=z,C>>=z;
C*=iv[y];
q_*=i;
}
ans^=i*s;
}
printf("%u",ans);
return 0;
}