FWT 異或卷積擴(kuò)展

異或卷積主要解決以下問(wèn)題：

給定長(zhǎng)度為 \(2^n\) 的序列 \(A,B\)，求序列 \(C=A*B\)，其中卷積的定義為：

我們實(shí)際上是渴望用類(lèi)似 \(FFT\) 的做法，現(xiàn)將上面的多項(xiàng)式通過(guò)變換改成點(diǎn)值，然后就可以用 \(O(n)\) 的時(shí)間內(nèi)計(jì)算乘法。即我們需要一個(gè)變換 \(FWT\) 滿(mǎn)足：

我們把上面的式子稱(chēng)為異或卷積的 定義式。

同時(shí)，我們規(guī)定 \(FWT\) 應(yīng)該是線性變換，也就是說(shuō)，我們考慮構(gòu)造一個(gè)矩陣 \(g\)，滿(mǎn)足：

如何構(gòu)造？我們把上面的式子代入我們的定義式，可以得到：

對(duì)比左右式子，我們可以只需要讓 \(g\) 滿(mǎn)足 \(g_{k,i}g_{k,j}=g_{k,i\oplus j}\) 即可。

同時(shí)考慮到異或?qū)τ诙M(jìn)制位下的每一位都是獨(dú)立的，所以我們只需要考慮同一位的 \(4\) 種情況。

因?yàn)槲覀冞€要做逆變換，所以需要保證這個(gè)矩陣一定是滿(mǎn)秩的，也就是說(shuō)其有逆矩陣。那么我們可以輕易構(gòu)造出一個(gè)矩陣：

而這個(gè)矩陣的逆為：

而我們?cè)诰唧w實(shí)現(xiàn)中可以從小到大對(duì)于每個(gè)二進(jìn)制位做一個(gè)這樣的變換。

通過(guò)以上兩個(gè)矩陣我們可以構(gòu)造出各自的 \(g\) 矩陣出來(lái)，以第一個(gè)矩陣為例子，我們?cè)O(shè)這個(gè)矩陣為 \(A\)，那么 \(4\times 4\) 的矩陣可以構(gòu)造為：

容易發(fā)現(xiàn)這仍然是滿(mǎn)足性質(zhì)的。（任取第二列同一行的兩個(gè)數(shù)就可以簡(jiǎn)單證明）。
并且無(wú)論擴(kuò)展多上次，用第一個(gè)矩陣擴(kuò)展出來(lái)的，它的逆矩陣一定是用第二個(gè)矩陣擴(kuò)展出來(lái)的，這個(gè)可以用歸納簡(jiǎn)單證明。

• 定理 \(1\)：\(FWT\) 的每一項(xiàng)滿(mǎn)足：

• 其中 \(|a|\) 表示 \(a\) 的二進(jìn)制表示下 \(1\) 的個(gè)數(shù)。

• 證明：根據(jù)我們構(gòu)造出來(lái)的 \(g\) 矩陣可以歸納證明只有當(dāng) \(|i\&j|\) 為奇數(shù)時(shí)才是 \(-1\)。所以上面的式子顯然成立。

注意我們構(gòu)造的 \(FWT\) 是線性變換，所以我們有 \(FWT(A+B)=FWT(A)+FWT(B)\)。

FWT 或卷積并卷積的擴(kuò)展

首先是通項(xiàng)公式：

所以：

• 做或卷積相當(dāng)于做高維前綴和，而做或卷積的逆相當(dāng)于做高維前綴差分。
• 做并卷積相當(dāng)于做高維后綴和，而做并卷積的逆相當(dāng)于做高維后綴差分。

證明很好證明，只需要從或卷積和并卷積的定義入手即可。

同時(shí)，這也證明了 FWT 和 FMT 本質(zhì)上來(lái)說(shuō)是一個(gè)東西。而且 FWT 能做的更多。

K 進(jìn)制 FWT

所謂 \(K\) 進(jìn)制 \(FWT\) 就是把 \(\oplus\) 換成 \(\bmod K\) 下的加法，也就是 \(K\) 進(jìn)制不進(jìn)位加法。我們下面用 \(\oplus_k\) 來(lái)替代。

所以相當(dāng)于我們是要求解：

我們同樣利用 \(g_{i,j}\) 來(lái)進(jìn)行變換，通過(guò)進(jìn)行和上面類(lèi)似的推導(dǎo)，我們可以得到 \(g\) 需要滿(mǎn)足 \(g_{x,i}g_{x,j}=g_{x,i\oplus_k j}\)，通過(guò)人類(lèi)智慧的構(gòu)造，我們可以構(gòu)造出一下矩陣：

而這個(gè)矩陣的逆矩陣應(yīng)該為：

證明只需要把兩個(gè)矩陣相乘即可，這樣時(shí)間復(fù)雜度應(yīng)該為：

\(T(n)=kT(\frac{n}{k})+nk=O(nk\log_kn)\)