FWT学习笔记
0.参考文献
参考文献
1.FWT的定义与证明
首先fwt是解决一类二进制下与或非运算的卷积问题的
也就是形如
$$
C_i=\sum_{j\oplus k = i}A_j \times B_k
$$
使用fwt可以nlogn的进行计算
但是实际上似乎遇到一些任意进制下且不进位的卷积操作都可以考虑使用这种思想进行处理
1.1 AND
$$
c_i = \sum_{i=j|k}a_jb_k
$$
有
$$
j|i=i,k|i=i,(j|k)|i=i
$$
因为
$$
(j|k)|j = (j|k),(j|k)|i = (j|k)
$$
构造
$$
\begin{aligned}
fwt_{ai} &= \sum_{j|i=i}a_j\\
fwt_{bi} &= \sum_{k|i=i}b_k\\
fwt_{ci} &= \sum_{(j|k)|i=i}a_j b_k
\end{aligned}
$$
有
$$
\begin{aligned}
fwt[a]\times fwt[b]
&=(\sum_{j|i=i}a[j]))\times(\sum_{k|i=i}b[k])) \\
&=\sum_{j|i=i}\sum_{k|i=i}a_j b_k\\
&=\sum_{(j|k)|i=i}a_j b_k\\
&=fwt[c]
\end{aligned}
$$
如何以nlogn的复杂度计算fwt & ifwt
令$a_0$为a中下标最高位为0的部分，$a_1$为a中下标最高位为1的部分
$$
fwt[a]=merge(fwt[a_0],fwt[a_0]+fwt[a_1])
$$
1.2 OR >> 证明与AND相同
1.3 XOR
这里构造了不同于OR/AND的变换
定义$x\otimes y = popcount(x\&y)%2$
其中$popcount(x)$为x在二进制下1的个数
显然该运算满足
$$
(i\otimes j)\ xor\ (i\otimes k)=i\otimes(j\ xor \ k)
$$
构造
$$
fwt_{ai} = \sum_{i\otimes j =0}a_jb_k
$$
有
$$
\begin{aligned}
fwt[a]\times fwt[b]&=(\sum_{i\otimes j =0}a_j-\sum_{i\otimes j =1}a_j)\times(\sum_{i\otimes j =0}b_k-\sum_{i\otimes j =1}b_k)\\
&=(\sum_{i\otimes j=0}a_j)(\sum_{i\otimes k=0}b_k)-(\sum_{i\otimes j=0}a_j)(\sum_{i\otimes k=1}b_k)-(\sum_{i\otimes j=1}a_j)(\sum_{i\otimes k=0}b_k)+(\sum_{i\otimes j=1}a_j)(\sum_{i\otimes k=1}b_k)\\
&=(\sum_{i\otimes(j\ xor\ k)=0}a_jb_k-\sum_{i\otimes(j\ xor\ k)=1}a_jb_k)\\
&=fwt[c]
\end{aligned}
$$
那么
$$
\begin{aligned}
fwt[a]&=merge(fwt[a_0]+fwt[a_1],fwt[a_0]-fwt[a_1])\\
a&=merge(\frac{a_0+a_1}{2},\frac{a_0-a_1}{2})
\end{aligned}
$$
2.代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f,MAXN = 1<<17|1,P = 998244353;
int n,inv2=(P+1)>>1;
template <typename _TP>
inline _TP qread(_TP &X){
char ch=0;int w;X=0;
while(!isdigit(ch)){w=ch=='-';ch=getchar();}
while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
X=w?-X:X;
return X;
}
int A[MAXN],B[MAXN],a[MAXN],b[MAXN];
inline void cpy(){
memcpy(a,A,sizeof(A));
memcpy(b,B,sizeof(B));
}
inline void mul(){
for(int i=1;i<=n;i++){
a[i]=(a[i]*b[i])%P;
}
}
inline void PRINT(){
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<'\n';
}
inline void fwtOr(int *a,const int opt){
for(int i=1;i<n;i<<=1){
for(int p=i<<1,j=1;j<=n;j+=p){
for(int k=0;k<i;k++){
a[i+j+k]=(a[i+j+k]+a[j+k]*opt+P)%P;
}
}
}
}
inline void fwtAnd(int *a,const int opt){
for(int i=1;i<n;i<<=1){
for(int p=i<<1,j=1;j<=n;j+=p){
for(int k=0;k<i;k++){
a[j+k]=(a[j+k]+a[i+j+k]*opt+P)%P;
}
}
}
}
inline void fwtXor(int *a,const int opt){
for(int i=1;i<n;i<<=1){
for(int p=i<<1,j=1;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)%P;
a[i+j+k]=(X+P-Y)%P;
a[j+k]=(a[j+k]*opt)%P;
a[i+j+k]=(a[i+j+k]*opt)%P;
}
}
}
}
signed main(){
qread(n);
n=1<<n;
for(int i=1;i<=n;i++){
qread(A[i]);
}
for(int i=1;i<=n;i++){
qread(B[i]);
}
cpy();fwtOr(a,1),fwtOr(b,1),mul(),fwtOr(a,-1),PRINT();
cpy();fwtAnd(a,1),fwtAnd(b,1),mul(),fwtAnd(a,-1),PRINT();
cpy();fwtXor(a,1),fwtXor(b,1),mul(),fwtXor(a,inv2),PRINT();
return 0;
}
|
