题意
给定非负整数 \(n,x,y\)，对于所有满足 \(\sum\limits_{i=1}^{n}a_i=x\) 并且 \(\text{OR}_{i=1}^{n}a_i=y\) 的 \(\{a_n\}\)，求 \(\bigoplus\limits_{i=1}^{n}a_i\) 的异或和。
\(n\le 2^{40},x\le 2^{60},y\le 2^{20}\)。
题解
首先根据对称性，当 \(n\) 为偶数时，答案为 \(0\)。所以只考虑 \(n\) 为奇数的情况，为 \(a_1\) 的异或和。
拆位，对每一位 \(t\)，计算 \(a_1\) 的第 \(t\) 位为 \(1\) 的方案数 \(\text{mod}\ 2\) 的结果。此时显然 \(\bigoplus\limits_{i=1}^{n}a_i\) 第 \(t\) 位为 \(1\)。
考虑容斥，设 \(g(y)\) 为按位或为 \(y\) 的方案数，\(f(y)\) 为按位或为 \(y\) 的子集的方案数，显然 \(f(y)=\sum\limits_{y'\subseteq y}g(y')\)，反演结论得到 \(g(y)=\sum\limits_{y'\subseteq y}(-1)^{|y|-|y'|}f(y')\)，前提是 \(y'\) 第 \(t\) 位为 \(1\)。
由于我们只需要得到 \(g(y)\) 的奇偶性，所以我们可以将式子变为 \(g(y)\equiv\bigoplus\limits_{y'\subseteq y}f(y')\mod 2\)。
因为钦定 \(a_1\) 的第 \(t\) 位为 \(1\)，我们可以让 \(a_1\) 减去 \(2^t\)，此时 \(\sum\limits_{i=1}^{n}a_i=x-2^t\)。 由 \(\text{Lucas}\) 定理推论（组合数奇偶性定理）与 \(\text{Vandermonde}\) 卷积公式得：
\[\begin{aligned}f(y)&=\sum\limits_{\sum\limits a_i=x-2^t}[a_1\subseteq y-2^t][a_2\subseteq y][a_3\subseteq y]...[a_n\subseteq y]\\&\equiv\sum\limits_{\sum a_i=x-2^t}\dbinom{y-2^t}{a_1}\dbinom{y}{a_2}\dbinom{y}{a_3}...\dbinom{y}{a_n}\mod 2\\&\equiv\dbinom{ny-2^t}{x-2^t}\mod 2\\&\equiv [x-2^t\subseteq ny-2^t]\mod 2\end{aligned} \]所以答案即为：
\[\begin{aligned}\sum\limits_{t}2^tf(y)&=\sum\limits_t 2^t\bigoplus\limits_{y'\subseteq y,2^t\in y'}g(y')\\&=\sum\limits_t 2^t\bigoplus\limits_{y'\subseteq y,2^t\in y'}[x-2^t\subseteq ny'-2^t]\end{aligned} \]\(O(y\log y)\) 枚举 \(t,y'\) 即可。
标签：dbinom,limits,Sequence,sum,bigoplus,Koxia,mod,subseteq,CF1770F From： https://www.cnblogs.com/Ender32k/p/17569006.html