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