CF1770F Koxia and Sequence 做题记录

给定非负整数 $n,x,y$，对于所有满足 $\sum \limits_{i=1}^n a_i=x$，所有 $a_i$ 按位或和为 $y$ 的序列 $a$，求出 $\oplus_{i=1}^n a_i$ 的异或和。

$1\le n\le 2^{40}$，$0\le x< 2^{60}$，$0\le x< 2^{20}$。

不难发现由于可以任意调换位置，所以所有 $a_i$ 本质相同，也就是说，$n$ 为偶数时答案为 $0$。

考虑 $n$ 为奇数的情况，此时只需要统计所有 $a_1$ 的异或和即可。

考虑拆位，对每个 $i$ 计算 $a_1$ 第 $i$ 位为 $1$ 的方案数 $\text{mod }2$ 的结果 $cnt_i$，则答案即为 $\sum 2^icnt_i$。

考虑通过容斥计算 $cnt_i$，设 $f(y')$ 表示 $a_i$ 的或和为 $y'$ 的子集且 $a_1$ 第 $i$ 位为 $1$ 的方案数，则：

$cnt_i=\oplus_{y'\subseteq y}(-1)^{|y|-|y'|}f(y')=\oplus_{y'\subseteq y}f(y')$

考虑计算 $f(y')$，由于 $a_1$ 第 $i$ 位一定为 $1$，所以不妨令 $a_1\to a_1-y^i$，则有：

$f(y')=\sum\limits_{a_1+a_2+\dots+a_n=x-2^i}[a_1\subseteq (y'-2^i)]\prod\limits_{i=2}^n[a_i\subseteq y']\mod 2$

注意到 $\binom{n}{m}\text{ mod }2=[m\subseteq n]$，所以：

$\begin{aligned} f(y')&=\sum\limits_{a_1+a_2+\dots+a_n=x-2^i}\binom{y'-2^i}{a_1}\prod\limits_{i=2}^n\binom{y'}{a_i}\mod 2\\ &=\binom{ny'-2^i}{x-2^i}\mod 2\\ &=[(x-2^i)\subseteq(ny'-2^i)]\\ \end{aligned}$

所以答案为：

$\sum 2^i\oplus_{y'\subseteq y}[(x-2^i)\subseteq(ny'-2^i)]$

时间复杂度 $O(y\log y)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

long long n,x;
int y;

int main()
{
	scanf("%lld%lld%d",&n,&x,&y);
	if(n&1^1) return puts("0"),0;
	int ans=0;
	for(int i=0;i<20;i++)
	{
		int f=0;
		for(int j=y;j>0;j=(j-1)&y)
		{
			if(j>>i&1^1) continue;
			f^=((x-(1<<i))|(n*j-(1<<i)))==(n*j-(1<<i));
		}
		ans+=f<<i;
	}
	printf("%d\n",ans);
	return 0;
}