FMT/FWT学习笔记
FMT/FWT是算法竞赛中求or/and/xor卷积的算法，数据处理中也有应用。
网上的命名方法有很多。
这里我们选这个博客的，把AND/OR命名为FMT，XOR命名为FWT
如果是整数，我们认为(cup)和(cap)运算是二进制下的，也就是( ext{|和&})，这可以帮我们理解之后的集合幂级数。
FMT 快速莫比乌斯变换 OR卷积
与FMT可以求出
[C=sum_i C_i=sum_isum_{jcup k=i}A_j*B_k=Acup B
]
因为前缀的并是前缀，容易得到过程是把A、B求子集前缀和，得到FMTor数组
[FMT(A)_n=sum_{i subseteq n}A_i
]
与FFT类似，FMTor数组直接乘起来就得到了C的FMTor数组，证明如下：
[FMT(A)_n * FMT(B)_n=sum_{i subseteq x} A_{i} sum_{j subseteq x} B_{j}=sum_{i, j subseteq x} A_{i} B_{j}=sum_{k subseteq x} sum_{i cup j=k} A_{i} B_{j}=FMT(C)_n
]
最后换回去（子集和变原数组）就得到了C
至于具体怎么算前缀和，挂张图，想必大家见过很多次了吧（箭头表示加法）
如上图，讨论这一层的1在不在下一个集合即可。
代码：
const int N = 2e5+200;
const ll mod = 998244353;
int a[N];
void FMTor(int *a,int n,int opt){
for(int l=2;l<=n;l<<=1){
int m=l>>1;
for(int *g=a;g!=a+n;g+=l){
for(int k=0;k<m;k++){
if(opt==1) g[k+m]=(g[k+m]+g[k])%mod;
else g[k+m]=(g[k+m]-g[k]+mod)%mod;
}
}
}
}
跟FFT非常的像...
AND卷积
[C=sum_i C_i=sum_isum_{jcap k=i}A_j*B_k=Acap B
]
然后猜测FMTand为后缀和（后缀的交为后缀），
[FMT(A)_n=sum_{nsubseteq i} A(i)
]
同样的，证明：
[FMT(A)_n * FMT(B)_n=sum_{nsubseteq i} A_isum_{nsubseteq j} B_j=sum_{nsubseteq i,j} A_i*B_j=sum_{nsubseteq x}sum_{icap j=x}A_i*B_j=FMT(C)_n
]
和OR是不是有几分相似？
const int N = 2e5+200;
const ll mod = 998244353;
int a[N];
void FMTand(int *a,int n,int opt){
for(int l=2;l<=n;l<<=1){
int m=l>>1;
for(int *g=a;g!=a+n;g+=l){
for(int k=0;k<m;k++){
if(opt==1) g[k]=(g[k]+g[k+m])%mod;
else g[k]=(g[k]-g[k+m]+mod)%mod;
}
}
}
}
快速沃尔什变换（FWT/XOR卷积)
这个稍微难点
我们要求
[C=sum_i C_i=sum_isum_{joplus k=i}A_j*B_k=Aoplus B
]
这里的FWT数组不是那么显然，考虑构造。
由于线性相关，令
[FWT(A)_x=sum_{i=0}^ng(x,i)A_i
]
那么
[sum_{i=0}^{n} g(x, i) C_{i}=sum_{j=0}^{n} g(x, j) A_{j} sum_{k=0}^{n} g(x, k) B_{k}
]
带入C的定义，
[sum_{j=0}^{n} sum_{k=0}^{n} g(x, j oplus k) A_{j} B_{k}=sum_{j=0}^{n} sum_{k=0}^{n} g(x, j) g(x, k) A_{j} B_{k}
]
对比系数，
[g(x,joplus k)=g(x,j)g(x,k)
]
异或有一系列性质：
-
((jcap x)oplus (kcap x)=(joplus k)cap x)
不知道这个的可以讨论一波：在第(i)位，
[egin{array}{|c|c|c|c|c|c|c|c|}j & k &x &jcap x &kcap x&(jcap x)oplus (kcap x)&j oplus k&(joplus k)cap x\0&0&0&0&0&0&0&0\0&0&1&0&0&0&0&0\0&1&0&0&0&0&1&0\0&1&1&0&1&1&1&1\1&0&0&0&0&0&1&0\1&0&1&1&0&1&1&1\1&1&0&1&1&0&0&0\1&1&1&1&1&0&0&0\end{array} ] -
异或前后1的个数奇偶性不变（对吧）
那么我们定义(|x|)为二进制下集合大小，即1的个数，g就可以赋值了
[g(x, i)=(-1)^{|i cap x|}
]
[FWT(A)_{x}=sum_{i=0}^{n}(-1)^{|i cap x|} A_{i}
]
考虑怎么递推算这个东西，考虑加不加上区间长度i
由于枚举i为2的次幂从小到大，新加上i集合大小一定加一，系数乘负一，否则不变。
那么有：
[A[j+k]=A_0[j+k]+A_0[j+k+i]\A[j+k+i]=A_0[j+k]-A_0[j+k+i]\
]
反过来，解方程可以得到
[A_0[j+k]=frac{A[j+k]+A[j+k+i]}{2}\A_0[j+k+i]=frac{A[j+k]-A_[j+k+i]}{2}\
]
代码：
const int N = 2e5+200;
const int mod = 998244353;
const int inv2 = 499122177;
int a[N];
void FWT(int *a,int n,int opt){
for(int l=2;l<=n;l<<=1){
int m=l>>1;
for(int *g=a;g!=a+n;g+=l){
for(int k=0;k<m;k++){
ll t=g[k+m];
g[k+m]=(g[k]-g[k+m]+mod)%mod;
g[k]=(g[k]+t)%mod;//草，有蝴蝶变换内味了
//提醒一下这和FFT的区别：没有乘单位根
if(opt==-1) g[k]=1ll*g[k]*inv2%mod,g[k+m]=1ll*g[k+m]*inv2%mod;
//而且反演的时候也不一样
}
}
}
}
就愉快地学完啦！是不是比FFT简单