题意
给定非负整数 \(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}\) 卷积公式得：
所以答案即为：
\(O(y\log y)\) 枚举 \(t,y'\) 即可。