FMT/FWT

用處

處理一些位運算卷積，\(O(n2^n)\)

\[c_i=\sum_{k \oplus j=i} a_k\times b_j \]

大體思想

構造某種映射，使得能夠 \(O(n\log n)\) 内得到變換，假設原數列為 \({a_n}\)，新數列就是 \({fwt[a]_i}\)。

然後知道了 \({fwt[a]_i}\) 和 \({fwt[b]_i}\)，能 \(O(n)\) 得到 \({fwt[c]_i}\)

最後還能夠 \(O(n\log n)\) 将 \(fwt[c]_i\) 變換為 \(c_i\)

其實和 FFT 很像，就是解析式到點值再到解析式。

構造方法

Or

構造 \(fwt[a]_i=\sum_{j|i=i} a_j\)，也就是對 \(i\) 的所有子集求和。

這個構造有性質如下：

\[\begin{align} fwt[a]_i\times fwt[b]_i&=\sum_{j|i=i} \sum_{k|i=i} a_j\times b_k \\ &=\sum_{(j|k)|i=i} a_j\times b_k \\ &=fwt[c]_i \end{align} \]

假設現在處理完了前 \(w-1\) 位的 \(fwt[c]_i\)，考慮怎麼加入第 \(w\) 位的貢獻。如果一個數的第 \(w\) 位是 0 ，那麼它的或卷積是不會變的，如果是 1，那麼答案就要累加上最高位為 1 的卷積。然後逆變換也是類似的，隻是符号反過來。

\[fwt[a]_i=merge(fwt[a_0]_i,fwt[a_0]_i+fwt[a_1]_i) \]

\(merge\) 表拼接。

void Or(int n,ll *a,bool op){
    for(int w=2,l=1;w<=n;w<<=1,l<<=1)
    for(int j=0;j<n;j+=w)
    for(int k=0;k<l;k++)
        a[j|k|l]=(a[j|k|l]+(op? -1:1)*a[j|k]+Mod)%Mod;
}
           

And

與卷積與或卷積類似，有

\[fwt[a]_i=merge(fwt[a_0]_i+fwt[a_1]_i,fwt[a_0]_i) \]

void And(int n,ll *a,bool op){
    for(int w=2,l=1;w<=n;w<<=1,l<<=1)
    for(int j=0;j<n;j+=w)
    for(int k=0;k<l;k++)
        a[j|k]=(a[j|k]+(op? -1:1)*a[j|k|l]+Mod)%Mod;
}
           

Xor

構造運算 \(x\otimes y=count(x\&y) \bmod 2\)

有性質

\[(x\otimes y) \ xor \ (x\otimes z)=x\otimes(y^z) \]

可以構造變換 \(fwt[a]_i=\sum_{i\otimes j=0} a_j-\sum_{i\otimes j=1}a_j\)

得到

\[fwt[a]_i=merge(fwt[a_0]_i+fwt[a_1]_i,fwt[a_0]_i-fwt[a_1]_i) \]

void Xor(int n,ll *a,ll op){
    ll x,y;
    for(int w=2,l=1;w<=n;w<<=1,l<<=1)
    for(int j=0;j<n;j+=w)
    for(int k=0;k<l;k++)
        x=(a[j|k]+a[j|k|l])%Mod*op%Mod,
        y=(a[j|k]-a[j|k|l]+Mod)%Mod*op%Mod,
        a[j|k]=x,a[j|k|l]=y;
}