首先根据对称性,\(n\) 为偶数的时候直接输出 \(0\),证明显然。
考虑 \(n\) 为奇数的情况,显然答案等于所有符合条件的数组的 \(a_1\) 的异或和。容斥。记 \(f_i\) 表示所有数按位与是 \(i\) 的子集的答案的异或和,那么由于异或运算只与奇偶性有关,答案可以写作 \(\oplus_{y\subseteq y'}f_{y'}\),于是问题进一步转化为怎样快速求出 \(f_{y'}\)。
依次考虑每一位,计算 \(a_1\) 在 \(2^i\) 位为 \(1\) 的方案数的奇偶性。推推式子吧:
\[\begin{aligned}
&\sum\limits_{\sum a_i=x-2^i}[a_1\subseteq y'-2^i][a_2\subseteq y'][a_3\subseteq y']\cdots[a_n\subseteq y']\\
=&\sum\limits_{\sum a_i=x-2^i}\dbinom{y'-2^i}{a_1}\dbinom{y'}{a_2}\cdots\dbinom{a_n}{y'}\bmod 2\\
=&\dbinom{ny'-2^i}{x-2^i}\bmod 2\\
=&[(x-2^i)\subseteq (ny'-2^i)]
\end{aligned}
\]
然后就做完了。代码 250B。
#include<bits/stdc++.h>
int64_t n,x,y,res=0;
int main(){
scanf("%lld%lld%lld",&n,&x,&y);if(n%2==0)return puts("0"),0;
for(int i=0;i<20;i++)for(int j=0;j<=y;j++)res^=(((j&y)==j)&&(j>>i&1)&&(((x-(1<<i))&(n*j-(1<<i)))==(x-(1<<i))))<<i;
printf("%lld\n",res);
}