有 n 个数组,每个数组里有 x 个 ai、y 个 bi 和 z 个 ci,保证 0≤ai,bi,ci<2k。
对于每一个 0≤t<2k,求有多少种从 n 个数组中分别选一个数的方式,使得这些数异或起来等于 t,对 998244353 取模。
1≤n≤105,1≤k≤17。
首先显然可以求出 Bi=FWT(Ai) 点乘起来再求 IFWT,但是这样时间复杂度为 O(nk2k),显然会 T。
发现 Bi,j=Cj,aix+Cj,biy+Cj,ciz,而且 Xor 卷积满足 Ci,j=(−1)∣i&j∣(∣a∣ 为 a 二进制表示中 1 的个数),所以有 Bi,j=(−1)∣j&ai∣x+(−1)∣j&bi∣y+(−1)∣j&ci∣z。
由于异或有自反性,所以考虑令 ai,bi,ci 都异或上 ai,最后求答案时再把下标异或上 ⊕ai。则有 Bi,j=x+(−1)∣j&bi∣y+(−1)∣j&ci∣z。
此时 Bi,j 共有四种取值,考虑对于每一个 (∏Bi)j 求出每种取值分别的数量 c1,c2,c3,c4,则 (∏Bi)j=(x+y+z)c1(x+y−z)c2(x−y+z)c3(x−y−z)c4,然后做 IFWT。
考虑列方程求解 c1,c2,c3,c4,只需要列出四条一次方程即可。
首先有 c1+c2+c3+c4=n。(1)
接下来考虑利用 Bi,j=x+(−1)∣j&bi∣y+(−1)∣j&ci∣z 的性质:
-
由于 FWT(A)+FWT(B)=FWT(A+B),所以可以令 Fi,j=[j=bi],此时 FWT(Fi)j=(−1)∣j&bi∣。
那么设 p1=∑FWT(Fi)j=FWT(∑Fi)j=∑(−1)∣j&bi∣,则根据 y 的系数得 c1+c2−c3−c4=p1。(2)
-
令 Fi,j=[j=ci],此时 FWT(Fi)j=(−1)∣j&ci∣。
设 p2=FWT(∑Fi)j=∑(−1)∣j&ci∣,则根据 z 的系数得 c1−c2+c3−c4=p2。(3)
-
令 Fi,j=[j=bi⊕ci],此时 FWT(Fi)j=(−1)∣j&bi∣(−1)∣j&ci∣。
设 p3=FWT(∑Fi)j=∑(−1)∣j&bi∣(−1)∣j&ci∣,则根据 y 和 z 的系数得 c1−c2−c3+c4=p3。(4)
则可以列出方程:
⎩⎪⎪⎪⎨⎪⎪⎪⎧c1+c2+c3+c4=nc1+c2−c3−c4=p1c1−c2+c3−c4=p2c1−c2−c3+c4=p3
解得:
⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧2(c3+c4)=n−p12(c3−c4)=p2−p3c1=4p1+p2+p3+nc2=4p1+n−p2−p3c3=4n−p1+p2−p3c4=4n−p1−p2+p3
c1,c2,c3,c4 可以用 long long
存下。
时间复杂度 O(n+k2k),代码如下:
#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;
}