题目
题目链接：https://www.luogu.com.cn/problem/P4717
给定长度为 (2^n) 两个序列 (A,B)，设
[C_i=sum_{joplus k = i}A_j imes B_k
]
分别当 (oplus) 是 or,and,xor 时求出 (C)。
思路
弃疗了，背板。
Blog
OR 的位矩阵及其逆矩阵
[egin{bmatrix} 1&0 \1 &1 end{bmatrix} egin{bmatrix}1 &0 \-1 & 1end{bmatrix}
]
AND 的位矩阵及其逆矩阵
[egin{bmatrix} 1&1 \0 &1 end{bmatrix} egin{bmatrix}1 &-1 \0 & 1end{bmatrix}
]
XOR 的位矩阵及其逆矩阵
[egin{bmatrix} 1&1 \1 &-1 end{bmatrix} egin{bmatrix}frac{1}{2} &frac{1}{2} \frac{1}{2} & -frac{1}{2}end{bmatrix}
]
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<17)+10,MOD=998244353,inv2=499122177;
const int C[7][2][2]=
{
{{0,0},{0,0}},
{{1,0},{1,1}},{{1,0},{MOD-1,1}},
{{1,1},{0,1}},{{1,MOD-1},{0,1}},
{{1,1},{1,MOD-1}},{{inv2,inv2},{inv2,MOD-inv2}}
};
int n;
ll f[N],g[N],X[N],Y[N];
void FWT(ll *f,int type)
{
for (int k=1;k<n;k<<=1)
for (int i=0;i<n;i+=(k<<1))
for (int j=0;j<k;j++)
{
ll x=f[i+j],y=f[i+j+k];
f[i+j]=(C[type][0][0]*x+C[type][0][1]*y)%MOD;
f[i+j+k]=(C[type][1][0]*x+C[type][1][1]*y)%MOD;
}
}
void Fmul(ll *f,ll *g,int type)
{
memcpy(X,f,sizeof(X));
memcpy(Y,g,sizeof(Y));
FWT(X,type); FWT(Y,type);
for (int i=0;i<n;i++) X[i]=X[i]*Y[i]%MOD;
FWT(X,type+1);
for (int i=0;i<n;i++) printf("%lld ",X[i]);
printf("
");
}
int main()
{
scanf("%d",&n);
n=(1<<n);
for (int i=0;i<n;i++) scanf("%lld",&f[i]);
for (int i=0;i<n;i++) scanf("%lld",&g[i]);
Fmul(f,g,1); Fmul(f,g,3); Fmul(f,g,5);
return 0;
}