模板題：

　　給定$n = 2^k$和兩個(gè)序列$A_{0..n-1}$, $B_{0..n-1}$，求

　　$$C_i = \sum_{j \oplus k = i} A_j B_k$$

　　其中$\oplus$是某一滿足交換律的位運(yùn)算，要求復(fù)雜度$O(nlogn)$。

---

?

快速沃爾什變換：

　　這是什么東西？能吃嗎？有用嗎？?請(qǐng)參閱SDOI2017r2d1-cut。

　　看到這個(gè)大家是不是立刻想到了快速傅里葉變換？

　　$$C_i = \sum_{j + k = i} A_j B_k$$

　　我們來想想離散傅里葉變換的本質(zhì)。

　　$$\begin{aligned}& DFT(A)_i \\
　　&= A(\omega_n^i)\\
　　&=\sum_{j=0}^{n-1} A_j * (\omega_n^i)^j\end{aligned}$$

　　令$f(n, i, j) = (\omega_n^i)^j$，則

　　$$DFT(A)_i = \sum_{j=0}^{n-1} A_j f(n, i, j)$$

　　它要滿足$DFT(A)_i * DFT(B)_i = DFT(C)_i$，即

　　$$(\sum_{j=0}^{n-1} A_j f(n, i, j))(\sum_{k=0}^{n-1} B_k f(n, i, k))=\sum_{l=0}^{n-1} C_l f(n, i, l)$$

　　$$\sum_{j=0}^{n-1} \sum_{k=0}^{n-1} A_j?B_k f(n, i, j) f(n, i, k))=\sum_{l=0}^{n-1} (\sum_{a+b=l} A_a B_b) f(n, i, l)$$

　　這時(shí)我們發(fā)現(xiàn)左右分別有$n^2$項(xiàng)，令對(duì)應(yīng)項(xiàng)系數(shù)相等，得

　　$$f(n, i, j)f(n, i, k) = f(n, i, j + k)$$

　　只要任意一個(gè)可以進(jìn)行逆變換且滿足上述條件的$f$都可以。

　　現(xiàn)在我們把上面的$+$都改成$\oplus$，就是離散沃爾什變換即

　　$$DWT(A)_i = \sum_{j=0}^{n-1} A_j?f(n,?i, j)$$

　　$$f(n,?i, j)f(n,?i, k) =?f(n,?i, j \oplus k)$$

　　怎么樣，是不是云里霧里頓開茅塞？

　　然而我們還需要變快，所以快速傅里葉變換采用

　　$$f(n, i, j) =?(\omega_n^i)^j$$

　　那它有什么優(yōu)美的性質(zhì)呢？

　　我們發(fā)現(xiàn)， 由于有折半引理，$f(n, i, j)$和$f(n, i+n/2, j)$可以同時(shí)從$f(n/2,i,j)$得來。

　　那么，從感性的角度，既然$\oplus$是一個(gè)位運(yùn)算，那么應(yīng)該更容易找到一個(gè)跟位運(yùn)算有關(guān)的$f$，這樣就自然有類似折半引理的東西使得我們可以做到上述事情。

　　例如，當(dāng)$\oplus$是位與時(shí)，可以取$f(i, j) = [i \& j = i]$， 即$j$的二進(jìn)制完全包含在$i$的二進(jìn)制里時(shí)為1，否則為0。

　　當(dāng)$\oplus$是位異或時(shí)， 可取$f(i, j) = (-1)^{count(i \& j)}$，其中$count(x)$表示$x$的二進(jìn)制表示中1的個(gè)數(shù)。

---

逆變換：

　　逆變換看上去好難啊。。。

　　其實(shí)逆變換還是比較簡(jiǎn)單的。因?yàn)榧热?f$跟位運(yùn)算有關(guān)，我就只需要考慮某一位就好了。

　　例如$\oplus$是位異或時(shí)我考慮$n=2,A=(a_0, a_1)$，

　　那么$DWT(A) = (da_0 = a_0 + a_1, da_1 = a_0 - a_1)$

　　我只需要解一個(gè)二元一次方程（把$da_0, da_1$作為常數(shù)， $a_0, a_1$作為變量）就可以解出$a_0, a_1$了。

　　沒了。

---

關(guān)于$f$函數(shù)的構(gòu)造：

　　$f$函數(shù)怎么構(gòu)造。。。和逆變換的方法差不多啊。。。只需要看$n=2$的情況就行（實(shí)際上一般就是$-1$的幾次冪，或者$0, 1, -1$)

　　如果記憶力好可以把所有都背下來，反正滿足交換律的位運(yùn)算只有8個(gè),其中還有2個(gè)是全一和全零。。。

　　把剩下六個(gè)列出來吧。。。（下列$f$函數(shù)均將第一個(gè)參數(shù)$n$省略， $[expr]$在布爾表達(dá)式$expr$為真時(shí)為1， 否則為0）

　　$\oplus$為位與： $f(i, j) = [j \& i = i]$.

　　$\oplus$為位或： $f(i, j) = [j \& i = j]$.

　　$\oplus$為位異或： $f(i, j) = (-1)^{count(i \& j)}$.

　　$\oplus$為位與非，位或非的時(shí)候把三個(gè)數(shù)組的下標(biāo)都取反就對(duì)應(yīng)位或和位與。

　　$\oplus$為同或時(shí)直接求位異或卷積再把$C$的下標(biāo)取反就行了。

---

吐槽：

　　明明可以背代碼我偏要說這么多。。。

　　只是因?yàn)殚e的慌。。。

　　當(dāng)然是要幫助大家更好的理解FWT。

　　至于為什么要滿足交換律。。。我才不會(huì)告訴你我還沒有搞出不滿足怎么做。

?　　有同學(xué)說FWT難以感性理解。。。我也不知道如何感性理解。。。

　　代碼嘛。。。直接拿FFT改一改就好了。。。

　　

1 void FWT(int *P, int len) { 2 if (len == 1) return; 3 FWT(P, len / 2); 4 FWT(P + len / 2, len / 2); 5 for (int i = 0; i < len / 2; ++i) { 6 int t1 = P[i], t2 = P[i + len / 2]; 7 P[i] = t1 + t2; 8 P[i + len / 2] = t1 - t2; 9 } 10 } 11 void IFWT(int *P, int len) { 12 if (len == 1) return; 13 for (int i = 0; i < len / 2; ++i) { 14 int t1 = P[i], t2 = P[i + len / 2]; 15 P[i] = (t1 + t2) / 2; 16 P[i + len / 2] = (t1 - t2) / 2; 17 } 18 IFWT(P, len / 2); 19 IFWT(P + len / 2, len / 2); 20 } FWT異或卷積

?

轉(zhuǎn)載于:https://www.cnblogs.com/y-clever/p/6875743.html

總結(jié)

以上是生活随笔為你收集整理的Fast Walsh-Hadamard Transform——快速沃尔什变换的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。