CF1119H Triple 做题记录

nn 个数组,每个数组里有 xxaia_iyybib_izzcic_i,保证 0ai,bi,ci<2k0\le a_i,b_i,c_i<2^k

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

1n1051\le n\le 10^51k171\le k\le 17

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

发现 Bi,j=Cj,aix+Cj,biy+Cj,cizB_{i,j}=C_{j,a_i}x+C_{j,b_i}y+C_{j,c_i}z,而且 Xor 卷积满足 Ci,j=(1)i&jC_{i,j}=(-1)^{|i\&j|}a|a|aa 二进制表示中 11 的个数),所以有 Bi,j=(1)j&aix+(1)j&biy+(1)j&cizB_{i,j}=(-1)^{|j\&a_i|}x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z

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

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

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

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

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

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

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

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

    p2=FWT(Fi)j=(1)j&cip2=\text{FWT}(\sum F_i)_j=\sum (-1)^{|j\&c_i|},则根据 zz 的系数得 c1c2+c3c4=p2c1-c2+c3-c4=p2。(3)

  • Fi,j=[j=bici]F_{i,j}=[j=b_i\oplus c_i],此时 FWT(Fi)j=(1)j&bi(1)j&ci\text{FWT}(F_i)_j=(-1)^{|j\&b_i|}(-1)^{|j\&c_i|}

    p3=FWT(Fi)j=(1)j&bi(1)j&cip3=\text{FWT}(\sum F_i)_j=\sum (-1)^{|j\&b_i|}(-1)^{|j\&c_i|},则根据 yyzz 的系数得 c1c2c3+c4=p3c1-c2-c3+c4=p3。(4)

则可以列出方程:

{c1+c2+c3+c4=nc1+c2c3c4=p1c1c2+c3c4=p2c1c2c3+c4=p3\begin{cases} c1+c2+c3+c4=n\\ c1+c2-c3-c4=p1\\ c1-c2+c3-c4=p2\\ c1-c2-c3+c4=p3 \end{cases}

解得:

{2(c3+c4)=np12(c3c4)=p2p3c1=p1+p2+p3+n4c2=p1+np2p34c3=np1+p2p34c4=np1p2+p34\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,c4c1,c2,c3,c4 可以用 long long 存下。

时间复杂度 O(n+k2k)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;
}