一、题目
二、解法
你发现这个题是个 ( t FWT) 的魔改版，回忆一下我们正常的 ( t FWT) 只能做下面的式子：
[C[k]=sum_{i?j=k}A[i] imes B[j]
]
但是这个题离谱得给我们一次塞了三个位运算进去：
[C[k]=sum_{iand j=k}A[ioplus j] imes B[ior j]
]
这时候不要被吓到了，我们要尽量套用 ( t FWT) 的基本式子，令 (x=ioplus j,y=ior j) ，那么 (iand j=y-x) ，那么尝试把全部都换成 (x,y) ，对于一对确定的 ((x,y)) ，满足条件的 (i,j) 是有 (2^{bit(x)}) 对的（因为 (x) 为 (1) 的位置上有两种组合），还要注意因为是乱枚举的 ((x,y)) 所以 (xin y) ，那么式子变成了：
[C[k]=sum_{x,y}[y-x=k][yand x=x]B[y] imes A[x] imes 2^{bit(x)}
]
把减号也换成位运算，利用 (xin y) 的关系：
[C[k]=sum_{x,y}[yoplus x=k][yand x=x]B[y] imes A[x] imes 2^{bit(x)}
]
[C[k]=sum_{xoplus y=k}[yand x=x]B[y] imes A[x] imes 2^{bit(x)}
]
能套 ( t FWT) 的雏形已经出来了，现在就要解决这个讨厌的 (yand x=x) ，利用特殊的异或运算，可以转化成数位的关系：
[C[k]=sum_{xoplus y=k}[bit(y)-bit(x)=bit(k)]B[y] imes A[x] imes 2^{bit(x)}
]
这就变成完全能做的东西了，用类似子集卷积的方法就行了。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 600005;
const int MOD = 998244353;
#define ll long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,inv,ans,a[20][M],b[20][M],c[20][M],pw[M],bit[M];
void fwt(int *a,int n,int op)
{
for(int i=1;i<n;i<<=1)
for(int p=i<<1,j=0;j<n;j+=p)
for(int k=0;k<i;k++)
{
int x=a[j+k],y=a[i+j+k];
a[j+k]=(x+y)%MOD;
a[i+j+k]=(x-y+MOD)%MOD;
if(op==-1)
{
a[j+k]=1ll*a[j+k]*inv%MOD;
a[i+j+k]=1ll*a[i+j+k]*inv%MOD;
}
}
}
signed main()
{
n=read();m=1<<n;
inv=(MOD+1)/2;pw[0]=1;
for(int i=1;i<m;i++)
{
bit[i]=bit[i>>1]+(i&1);
pw[i]=pw[i-1]*2ll%MOD;
}
for(int i=0;i<m;i++)
a[bit[i]][i]=1ll*read()*pw[bit[i]]%MOD;
for(int i=0;i<m;i++)
b[bit[i]][i]=read();
for(int i=0;i<=n;i++)
fwt(a[i],m,1),fwt(b[i],m,1);
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<m;k++)
c[i-j][k]=(c[i-j][k]+1ll*b[i][k]*a[j][k])%MOD;
for(int i=0;i<=n;i++)
fwt(c[i],m,-1);
ll x=1;
for(int i=0;i<m;i++)
{
ans=(ans+x*c[bit[i]][i])%MOD;
x=x*1526%MOD;
}
printf("%d
",ans);
}