FMT/FWT學習筆記
- 2020 年 5 月 6 日
- 筆記
- 多項式——FWT/FMT
FMT/FWT學習筆記
FMT/FWT是演算法競賽中求or/and/xor卷積的演算法，數據處理中也有應用。
網上的命名方法有很多。
這裡我們選這個部落格的，把AND/OR命名為FMT，XOR命名為FWT
如果是整數，我們認為\(\cup\)和\(\cap\)運算是二進位下的，也就是\(\text{|和&}\)，這可以幫我們理解之後的集合冪級數。
FMT 快速莫比烏斯變換 OR卷積
與FMT可以求出
\[C=\sum_i C_i=\sum_i\sum_{j\cup k=i}A_j*B_k=A\cup 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_i\sum_{j\cap k=i}A_j*B_k=A\cap B
\]
\]
然後猜測FMTand為後綴和（後綴的交為後綴），
\[FMT(A)_n=\sum_{n\subseteq i} A(i)
\]
\]
同樣的，證明：
\[FMT(A)_n * FMT(B)_n=\sum_{n\subseteq i} A_i\sum_{n\subseteq j} B_j=\sum_{n\subseteq i,j} A_i*B_j=\sum_{n\subseteq x}\sum_{i\cap 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_i\sum_{j\oplus k=i}A_j*B_k=A\oplus 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,j\oplus k)=g(x,j)g(x,k)
\]
\]
異或有一系列性質：
-
\((j\cap x)\oplus (k\cap x)=(j\oplus k)\cap x\)
不知道這個的可以討論一波：在第\(i\)位，
\[\begin{array}{|c|c|c|c|c|c|c|c|}j & k &x &j\cap x &k\cap x&(j\cap x)\oplus (k\cap x)&j \oplus k&(j\oplus 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簡單
