快速沃爾什變換

（本文轉載自桃醬的算法筆記，原文戳鏈接，已獲得作者授權）

簡介

沃爾什轉換（Walsh Transform）是在頻譜分析上作為離散傅立葉變換的替代方案的一種方法。——維基百科

其實這個變換在信號處理中應用很廣泛，fft 是 double 類型的，但是 walsh 把信號在不同震盪頻率方波下拆解，因此所有的係數都是絕對值大小相同的整數，這使得不需要作浮點數的乘法運算，提高了運算速度。

所以，FWT 和 FFT 的核心思想應該是相同的，都是對數組的變換。我們記對數組 \(A\) 進行快速沃爾什變換後得到的結果為 \(FWT[A]\)。

那麼 FWT 核心思想就是：

我們需要一個新序列 \(C\)，由序列 \(A\) 和序列 \(B\) 經過某運算規則得到，即 \(C = A \cdot B\)；

我們先正向得到 \(FWT[A], FWT[B]\)，再根據 \(FWT[C]=FWT[A] \cdot FWT[B]\) 在 \(O(n)\) 的時間複雜度內求出 \(FWT[C]\)；

然後逆向運算得到原序列 \(C\)。時間複雜度為 \(O(n \log{n})\)。

在算法競賽中，FWT 是用於解決對下標進行位運算卷積問題的方法。

公式：\(C_{i} = \sum_{i=j \bigoplus k}A_{j} B_{k}\)

（其中 \(\bigoplus\) 是二元位運算中的某一種，\(*\) 是普通乘法）

FWT 的運算

FWT 之與（&）運算和或（|）運算

與運算和或運算的本質是差不多的，所以這裏講一下或運算，與運算也是可以自己根據公式 yy 出來的。

或運算

如果有 \(k=i|j\)，那麼 \(i\) 的二進制位為 \(1\) 的位置和 \(j\) 的二進制位為 \(1\) 的位置肯定是 \(k\) 的二進制位為 \(1\) 的位置的子集。

現在要得到 \(FWT[C] = FWT[A] * FWT[B]\)，我們就要構造這個 fwt 的規則。

我們按照定義，顯然可以構造 \(FWT[A] = A' = \sum_{i=i|j}A_{j}\)，來表示 \(j\) 滿足二進制中 \(1\) 為 \(i\) 的子集。

那麼顯然會有 \(C_{i} = \sum_{i=j|k}A_{j}*B_{k} \implies FWT[C] = FWT[A] * FWT[B]\)

那麼我們接下來看 \(FWT[A]\) 怎麼求。

首先肯定不能枚舉了，複雜度為 \(O(n^2)\)。既然不能整體枚舉，我們就考慮分治。

我們把整個區間二分，其實二分區間之後，下標寫成二進制形式是有規律可循的。

我們令 \(A_0\) 表示 \(A\) 的前一半，\(A_1\) 表示區間的後一半，那麼 \(A_0\) 就是 A 下標最大值的最高位為 \(0\)，他的子集就是他本身的子集（因為最高位為 \(0\) 了），但是 \(A_1\) 的最高位是 \(1\)，他滿足條件的子集不僅僅是他本身，還包最高位為 \(0\) 的子集，即

\[ FWT[A] = merge(FWT[A_0], FWT[A_0] + FWT[A_1]) \]

其中 merge 表示像字符串拼接一樣把它們拼起來，\(+\) 就是普通加法，表示對應二進制位相加。

這樣我們就通過二分能在 \(O(\log{n})\) 的時間複雜度內完成拼接，每次拼接的時候要完成一次運算，也就是説在 \(O(n\log{n})\) 的時間複雜度得到了 \(FWT[A]\)。

接下來就是反演了，其實反演是很簡單的，既然知道了 \(A_0\) 的本身的子集是他自己 (\(A_0 = FWT[A_0]\))，\(A_1\) 的子集是 \(FWT[A_0] + FWT[A_1]（A_1 = A_0' + A_1'\)），那就很簡單的得出反演的遞推式了：

\[ UFWT[A'] = merge(UFWT[A_0'], UFWT[A_1'] - UFWT[A_0']) \]

與運算

與運算類比或運算可以得到類似結論

\[ FWT[A] = merge(FWT[A_0] + FWT[A_1], FWT[A_1]) \]

\[ UFWT[A'] = merge(UFWT[A_0'] - UFWT[A_1'], UFWT[A_1']) \]

異或運算

最常考的異或運算。

異或的卷積是基於如下原理：

若我們令 \(i\And j\) 中 \(1\) 數量的奇偶性為 \(i\) 與 \(j\) 的奇偶性，那麼 \(i\) 與 \(k\) 的奇偶性異或 \(j\) 與 \(k\) 的奇偶性等於 \(i \operatorname{xor} j\) 與 \(k\) 的奇偶性。

對於 \(FWT[A]\) 的運算其實也很好得到。

公式如下：

\(A_{i} = \sum_{C_1}A_{j} - \sum_{C_2}A_{j}\)(\(C_1\) 表示 \(i \And j\) 奇偶性為 \(0\)，\(C_2\) 表示 \(i \And j\) 的奇偶性為 \(1\))

結論：

\[ FWT[A] = merge(FWT[A_0] + FWT[A_1], FWT[A_0] - FWT[A_1]) \]

\[ UFWT[A'] = merge(\frac{UFWT[A_0'] + UFWT[A_1']}{2}, \frac{UFWT[A_0'] - UFWT[A_1']}{2}) \]

同或運算

類比異或運算給出公式：

\(A_{i} = \sum_{C_1}A_{j} - \sum_{C_2}A_{j}\)(\(C_1\) 表示 \(i|j\) 奇偶性為 \(0\)，\(C_2\) 表示 \(i|j\) 的奇偶性為 \(1\))

\[ FWT[A] = merge(FWT[A_1] - FWT[A_0], FWT[A_1] + FWT[A_0]) \]

\[ UFWT[A'] = merge(\frac{UFWT[A_1'] - UFWT[A_0']}{2}, \frac{UFWT[A_1'] + UFWT[A_0']}{2}) \]

例題

【CF103329F】【XXII Opencup, Grand Prix of XiAn】The Struggle

給出一個橢圓 \(E\)，其中所有整點的座標均在 \([1,4 \cdot 10^6]\) 之間。求 \(\sum_{(x,y) \in E} (x \oplus y)^{33}x^{-2}y^{-1} \mod 10^9+7\) 的值。

題解

這是一道比較不裸的題，出題人提供了詳細的英文題解，具體請見此鏈接。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Xeonacid, nocriz
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用