题意简述
给定 \(n,x,y\)，定义序列 \(\{a_n\}\) 合法当且仅当 \(\sum_{i=1}^na_i=x\) 且 \(\operatorname{or}_{i=1}^n=y\)，你需要求出 \(\oplus_{a\ \text{is}\ \text{valid}} \oplus_{i=1}^n a_i\) 的值。
\(n<2^{40},x<2^{60},y<2^{20}\)。
分析
第一步：先做一波非常重要的分析
答案要求所有合法序列的所有数的异或，而因为一个合法序列翻转后也是合法序列，因此两个方案的贡献被抵消。那么只有回文序列才有可能有贡献。
若 \(n\) 为偶数，那么因为回文，所以会两两抵消，因此 \(n\) 为偶数时答案为 0。若 \(n\) 为奇数，则除最中间的数以外全部抵消，为表述方便我们令那一项是 \(a_1\)（你重排序列显然不会影响答案，实际上令啥或不令都无所谓），答案相当于求所有合法序列的 \(a_1\) 的异或和。
第二步：考虑如何计数
考虑要让序列符合两个条件。若让序列满足条件二，那么很难做一个使得 \(\sum a=x\) 的计数，所以考虑让 \(\sum a=x\)，对条件二计数。
按位考虑 \(a_1\) 每一位的贡献，由于是异或，我们只需要算出 \(a_1\) 那一位为 \(1\) 的方案数的奇偶性，为 1 就有贡献。发现直接让或结果等于 \(y\) 很难做，考虑容斥，答案就是 \(\sum_{y'\subseteq y} (-1)^{|y|-|y'|}f(y',i)\)，因为只需要奇偶性，所以答案就是 \(\oplus_{y'\subseteq y}f(y',i)\)，其中 \(f(y,i)\) 表示当序列或为 \(y\) 时 \(a_1\) 第 \(i\) 位是 \(1\) 的方案数。
第三步：求解 \(f(y,i)\)
引理：\([x\subseteq y]=\dbinom{y}{x}\bmod 2\)。
证明：根据卢卡斯定理，\(\dbinom{x}{y}\equiv\dbinom{\lfloor\frac{x}{2}\rfloor}{\lfloor\frac{y}{2}\rfloor}\dbinom{x\bmod 2}{y \bmod 2}\pmod 2\)，发现 \(\dbinom{x\bmod 2}{y \bmod 2}\) 只有在 \(x\bmod 2=0,y\bmod 2=1\) 时为 0。而整个求解的过程就是二进制分解的过程，所以 \(\dbinom{x}{y}\) 为 \(1\) 就相当于对于每一位，\(x\) 为 0 时 \(y\) 就不能为 1，等价于 \(y\) 是 \(x\) 子集。
而 \(f(y,i)=[2^i\subseteq y]\sum_{\sum a=x}[2^i\subseteq a_1]\prod_{i}[a_i\subseteq y]\)（后文为方便把 \([2^i\subseteq y]\) 省略），根据引理可以直接把原式子变成组合数式子（方便推导）：
\[f(y,i)=\sum_{\sum a=x}\dbinom{a_1}{2^i}\prod{i}\dbinom{y}{a_i} \]考虑将 \(\dbinom{a_1}{2^i}\) 扔到外面，把右面的 \(\dbinom{y}{a_1}\) 分离出来，那么 \(\dbinom{a_1}{2^i}\dbinom{y}{a_1}\) 就是经典的组合恒等式，它等于 \(\dbinom{y}{2^i}\dbinom{y-2^i}{a_1-2^i}\)，这样 \(\dbinom{y}{2^i}\) 就可以扔出 sigma 了：
\[f(y,i)=\dbinom{y}{2^i}\sum_{\sum a=x}\dbinom{y-2^i}{a_1-2^i}\dbinom{y}{a_2}\cdots \]引理：（范德蒙德卷积）\(\sum_{i}\dbinom{n}{r-i}\dbinom{m}{s+i}=\dbinom{n+m}{r+s}\)，证明用组合意义不难证明。注意这个 \(i\) 可以取组合数有定义下的任何值。
我们把它推广到多个组合数相乘的形式，就是 \(\sum_{a_1+a_2+\cdots+a_k=x}\dbinom{b_1}{a_1}\dbinom{b_2}{a_2}\cdots\dbinom{b_k}{a_k}=\dbinom{\sum b}{\sum a}\)，因为 \(a_i\) 可以取组合数有定义下的任何值。
我们把原式后面那坨 sigma 用范德蒙德卷积的推广合并掉，就是：
\[f(y,i)=\dbinom{y}{2^i}\dbinom{y-2^i+y+y+\cdots}{a_1-2^i+a_2+\cdots}=\dbinom{y}{2^i}\dbinom{ny-2^i}{x-2^i} \]把组合数化回原来的条件形式，\(f(y,i)\) 就等于 \([2^i\subseteq y][x-2^i\subseteq ny-2^i]\)，\(O(1)\) 的。
再把它代回容斥式子，\(a_1\) 第 \(i\) 位为 1 的方案数就可求，然后答案也很好求，然后就做完了。枚举 \(y\) 的子集和答案的二进制位，时间复杂度 \(O(y\log y)\)。
代码很好写。
int n,x,y;
bool In(int x,int y){return (x&y)==x;}
void solve_the_problem(){
n=rd(),x=rd(),y=rd();
if(n%2==0)return (void)P0;
int ans=0;
per(j,19,0){
int ret=0;
for(int i=y;i;i=(i-1)&y){
if(In((1<<j),i)&&In(x-(1<<j),n*i-(1<<j)))ret^=1;
}
ans+=ret*(1<<j);
}
write(ans);
}