CF1119H Triple 做题记录

有 $n$ 个数组，每个数组里有 $x$ 个 $a_i$、$y$ 个 $b_i$ 和 $z$ 个 $c_i$，保证 $0\le a_i,b_i,c_i<2^k$。

对于每一个 $0\le t<2^k$，求有多少种从 $n$ 个数组中分别选一个数的方式，使得这些数异或起来等于 $t$，对 $998244353$ 取模。

$1\le n\le 10^5$，$1\le k\le 17$。

首先显然可以求出 $B_i=\text{FWT}(A_i)$ 点乘起来再求 $\text{IFWT}$，但是这样时间复杂度为 $O(nk2^k)$，显然会 T。

发现 $B_{i,j}=C_{j,a_i}x+C_{j,b_i}y+C_{j,c_i}z$，而且 Xor 卷积满足 $C_{i,j}=(-1)^{|i\&j|}$（$|a|$ 为 $a$ 二进制表示中 $1$ 的个数），所以有 $B_{i,j}=(-1)^{|j\&a_i|}x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z$。

由于异或有自反性，所以考虑令 $a_i,b_i,c_i$ 都异或上 $a_i$，最后求答案时再把下标异或上 $\oplus a_i$。则有 $B_{i,j}=x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z$。

此时 $B_{i,j}$ 共有四种取值，考虑对于每一个 $(\prod B_{i})_j$ 求出每种取值分别的数量 $c1,c2,c3,c4$，则 $(\prod B_{i})_j=(x+y+z)^{c1}(x+y-z)^{c2}(x-y+z)^{c3}(x-y-z)^{c4}$，然后做 $\text{IFWT}$。

考虑列方程求解 $c1,c2,c3,c4$，只需要列出四条一次方程即可。

首先有 $c1+c2+c3+c4=n$。(1)

接下来考虑利用 $B_{i,j}=x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z$ 的性质：

• 由于 $\text{FWT}(A)+\text{FWT}(B)=\text{FWT}(A+B)$，所以可以令 $F_{i,j}=[j=b_i]$，此时 $\text{FWT}(F_i)_j=(-1)^{|j\&b_i|}$。

  那么设 $p1=\sum\text{FWT}(F_i)_j=\text{FWT}(\sum F_i)_j=\sum (-1)^{|j\&b_i|}$，则根据 $y$ 的系数得 $c1+c2-c3-c4=p1$。(2)

• 令 $F_{i,j}=[j=c_i]$，此时 $\text{FWT}(F_i)_j=(-1)^{|j\&c_i|}$。

  设 $p2=\text{FWT}(\sum F_i)_j=\sum (-1)^{|j\&c_i|}$，则根据 $z$ 的系数得 $c1-c2+c3-c4=p2$。(3)

• 令 $F_{i,j}=[j=b_i\oplus c_i]$，此时 $\text{FWT}(F_i)_j=(-1)^{|j\&b_i|}(-1)^{|j\&c_i|}$。

  设 $p3=\text{FWT}(\sum F_i)_j=\sum (-1)^{|j\&b_i|}(-1)^{|j\&c_i|}$，则根据 $y$ 和 $z$ 的系数得 $c1-c2-c3+c4=p3$。(4)

则可以列出方程：

$\begin{cases}c1+c2+c3+c4=n\\c1+c2-c3-c4=p1\\c1-c2+c3-c4=p2\\c1-c2-c3+c4=p3\end{cases}$

解得：

$\begin{cases}2(c3+c4)=n-p1\\2(c3-c4)=p2-p3\\c1=\frac{p1+p2+p3+n}{4}\\c2=\frac{p1+n-p2-p3}{4}\\c3=\frac{n-p1+p2-p3}{4}\\c4=\frac{n-p1-p2+p3}{4}\end{cases}$

$c1,c2,c3,c4$ 可以用 long long 存下。

时间复杂度 $O(n+k2^k)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int p=998244353,inv2=499122177;

inline int qpow(int x,long long y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline void FWT(int n,long long a[])
{
	for(int len=2;len<=n;len<<=1)
	{
		int mid=len>>1;
		for(int l=0;l<n-len+1;l+=len)
		{
			for(int k=0;k<mid;k++)
			{
				long long x=a[l+k],y=a[l+mid+k];
				a[l+k]=x+y;
				a[l+mid+k]=x-y;
			}
		}
	}
}

inline void IFWT(int n,int a[])
{
	for(int len=2;len<=n;len<<=1)
	{
		int mid=len>>1;
		for(int l=0;l<n-len+1;l+=len)
		{
			for(int k=0;k<mid;k++)
			{
				int x=a[l+k],y=a[l+mid+k];
				a[l+k]=(1ll*inv2*x%p+1ll*inv2*y%p)%p;
				a[l+mid+k]=(1ll*inv2*x%p+1ll*(p-inv2)*y%p)%p;
			}
		}
	}
}

int n,k;
int X,Y,Z;
int sm;
long long F1[1<<17],F2[1<<17],F3[1<<17];
int ans[1<<17];

int main()
{
	scanf("%d%d",&n,&k);
	scanf("%d%d%d",&X,&Y,&Z);
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		sm^=a,b^=a,c^=a;
		F1[b]++,F2[c]++,F3[b^c]++;
	}
	FWT(1<<k,F1),FWT(1<<k,F2),FWT(1<<k,F3);
	int v1=((long long)X+Y+Z)%p;
	int v2=((long long)X+Y-Z)%p;
	int v3=((long long)X-Y+Z)%p;
	int v4=((long long)X-Y-Z)%p;
	for(int i=0;i<(1<<k);i++)
	{
		long long p1=F1[i],p2=F2[i],p3=F3[i];
		long long c1=(p1+p2+p3+n)/4;
		long long c2=(p1+n-p2-p3)/4;
		long long c3=(n-p1+p2-p3)/4;
		long long c4=(n-p1-p2+p3)/4;
		ans[i]=(1ll*qpow(v1,c1)*qpow(v2,c2)%p*qpow(v3,c3)%p*qpow(v4,c4)%p+p)%p;
	}
	IFWT(1<<k,ans);
	for(int i=0;i<(1<<k);i++) printf("%d ",ans[i^sm]);
	printf("\n");
	return 0;
}
复制代码