Codeforces 1770F - Koxia and Sequence（容斥+组合恒等式逆用）

首先根据对称性，(n) 为偶数的时候直接输出 (0)，证明显然。

考虑 (n) 为奇数的情况，显然答案等于所有符合条件的数组的 (a_1) 的异或和。容斥。记 (f_i) 表示所有数按位与是 (i) 的子集的答案的异或和，那么由于异或运算只与奇偶性有关，答案可以写作 (oplus_{ysubseteq y"}f_{y"})，于是问题进一步转化为怎样快速求出 (f_{y"})。

依次考虑每一位，计算 (a_1) 在 (2^i) 位为 (1) 的方案数的奇偶性。推推式子吧：

[egin{aligned} &sumlimits_{sum a_i=x-2^i}[a_1subseteq y"-2^i][a_2subseteq y"][a_3subseteq y"]cdots[a_nsubseteq y"]\ =&sumlimits_{sum a_i=x-2^i}dbinom{y"-2^i}{a_1}dbinom{y"}{a_2}cdotsdbinom{a_n}{y"}mod 2\ =&dbinom{ny"-2^i}{x-2^i}mod 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
",res);
}