大概是个经典题，因为他被两次抬到山东省集的模拟赛。/jy

虽然有一次被魔改成了交互题。

信息论入门题。

枚举天数 $k$，考虑最后的局面（也就是我们得到的信息）。我们可以把所有熊的状态抽象成一个长度是 $n$ 的序列 $a$，$a_i$ 的值域是 $[0,k]$，其中 $0$ 表示这只熊最后是醒着的，否则表示这只熊在第 $a_i$ 天睡着了。额外的限制是这个序列最多有 $\min(p,n-1)$ 个不是 $0$ 的值。

那么枚举有多少个不是 $0$ 的数，本质不同的序列就有 $\sum\limits_{i=0}^{\min(p,n-1)}k^i\dbinom ni$ 种，显然答案不会超过这个值，但答案是否就是这个值呢？考虑构造一种方案使得一种酒的位置和一个序列一一对应。

发现确实是可以构造的。考虑先给每种酒的位置 $k$ 钦定一个对应的序列 $a_k$，在第 $j$ 天，如果第 $i$ 只熊还醒着，那么他会喝下所有 $a_{k,i}=j$ 的位置的桶里的液体。

这样构造的正确性是显然的，如果这只熊今天睡着了说明对应序列 $a_{k,i}=j$，否则 $a_{k,i}\neq j$，这样对于每个位置我们都能根据熊最终的状态得出序列对应位置的值，由于序列和酒的位置之间是双射，所以可以唯一确定一个答案，因此答案的上界就是答案的精确值。

接下来考虑怎么算，发现这题要求的是自然溢出，算组合数的时候不一定有逆元。但自然溢出等价于对 $2^{32}$ 取模，所以直接套上对 $p^k(p\in\mathrm{prime})$ 取模的方法，质因子 $2$ 拿出来单独处理即可，剩下的部分扩欧计算逆元。

预处理组合数之后就可以直接暴力 $O(pq)$ 扫一遍算答案了，时间复杂度 $O(p^2\log p+pq)$，比大部分题解的暴力约分复杂度优秀一点。虽然不是复杂度瓶颈。

#include<iostream>
#include<cstdio>
using namespace std;
#define int unsigned int
const long long mod=1ll<<32;
int n,p,q,val[201],ans;
inline void exgcd(long long a,long long b,long long &x,long long &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
inline int inv(long long w)
{
    long long x,y;
    exgcd(w,mod,x,y);
    return (int)((x+mod)%mod);
}
inline int calc(int m)
{
    int cnt=0,res=1;
    for(int i=n;i>=n-m+1;--i)
    {
        int len=__builtin_ctz(i);
        cnt+=len;
        res*=i>>len;
    }
    for(int i=1;i<=m;++i)
    {
        int len=__builtin_ctz(i);
        cnt-=len;
        res*=inv(i>>len);
    }
    return res*(1u<<cnt);
}
signed main()
{
    cin>>n>>p>>q;
    p=min(p,n-1);
    for(int i=0;i<=p;++i)
        val[i]=calc(i);
    for(int i=1;i<=q;++i)
    {
        int res=0,w=1;
        for(int j=0;j<=p;++j)
        {
            res+=w*val[j];
            w*=i;
        }
        ans^=i*res;
    }
    cout<<ans<<'\n';
    return 0;
}