有
个数组,每个数组里有 个 、 个 和 个 ,保证 。 对于每一个
,求有多少种从 个数组中分别选一个数的方式,使得这些数异或起来等于 ,对 取模。
, 。
首先显然可以求出
发现
由于异或有自反性,所以考虑令
此时
考虑列方程求解
首先有
接下来考虑利用
-
由于
,所以可以令 ,此时 。那么设
,则根据 的系数得 。(2) -
令
,此时 。设
,则根据 的系数得 。(3) -
令
,此时 。设
,则根据 和 的系数得 。(4)
则可以列出方程:
解得:
long long
存下。
时间复杂度
#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;
}
复制代码