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);
}
原文地址:https://www.cnblogs.com/tzcwk/p/Codeforces-1770F.html