题解

思路推导

固定聚会持续 $d$ 个夜晚。对任意一桶饮料，最后能够观察到的信息是：哪些熊睡着了，以及每只睡着的熊在哪一晚睡着。没有睡着的熊记为 $0$，睡着的熊可以取 $1$ 到 $d$ 中的一个夜晚。

最多只能有 $p$ 只熊睡着，同时必须至少留下一只醒着的熊。因此令 $P=\min(p,n-1)$，合法信息中非零位置至多有 $P$ 个。恰有 $k$ 只熊睡着时，先从 $n$ 只熊中选择这 $k$ 只，再分别选择睡着的夜晚，共有 $\binom nk d^k$ 种信息。于是

$$R_d=\sum_{k=0}^{P}\binom nk d^k.$$

这个上界可以达到。为每种合法信息安排一桶饮料；若该信息规定熊 $b$ 在第 $r$ 晚睡着，就让熊 $b$ 在第 $r$ 晚饮用对应的桶。无论哪一桶是葡萄酒，实际观察到的信息都与该桶的编号一一对应，并且睡着的熊数不超过 $P$。

做法

需要在模 $2^{32}$ 意义下求出 $\binom n0,\binom n1,\ldots,\binom nP$。模数不是质数，不能使用模逆元。

对每个 $k$，把组合数写成

$$\binom nk=\frac{n(n-1)\cdots(n-k+1)}{1\cdot2\cdots k}.$$

分别保存分子和分母的至多 $130$ 个因子。枚举分母因子与分子因子，用最大公因数不断约分。组合数本来是整数，所以最后所有分母都会变为 $1$。随后在无符号 $32$ 位整数中乘起剩余分子，溢出正好等价于对 $2^{32}$ 取模。

预处理全部组合数后，对每个 $d=1,2,\ldots,q$ 依次维护 $d^0,d^1,\ldots,d^P$，计算 $R_d$，再把 $dR_d$ 异或进答案。所有加法和乘法都使用无符号 $32$ 位整数。

正确性证明

每一桶葡萄酒都会产生一个由睡着熊集合及其睡着夜晚组成的信息。要保证不失败，该集合大小不超过 $p$ 且小于 $n$，所以不同桶至多对应公式中计数的全部合法信息，得到 $R_d$ 的上界。

上述构造为每个合法信息安排一桶，并让每只熊只在信息指定的夜晚饮用该桶。若这桶是葡萄酒，恰好会产生指定信息。不同桶的信息不同，熊能唯一识别葡萄酒桶；睡着的熊不超过 $P$，也至少留有一只醒着。因此上界能够达到，公式成立。

因子约分只在整数表示中同时除去分子与分母的公因数，不改变组合数；最终乘积在无符号 $32$ 位整数中的值就是组合数模 $2^{32}$。逐日代入已证明的公式并按定义异或，所以算法输出正确。

部分分算法

当 $n\le20$ 时，可以枚举全部熊的子集，按子集大小统计合法信息的系数，再逐日计算多项式。

当 $n\le200000$ 时，可以用 Pascal 递推从后向前更新组合数，避免模除法。

复杂度分析

组合数的因子约分耗时 $O(P^3\log n)$，逐日计算耗时 $O(Pq)$。总时间复杂度为 $O(P^3\log n+Pq)$，空间复杂度为 $O(P)$。