快速沃尔什变换「FWT」
处理问题
$$
C_i = \sum\limits_{i \oplus j} A_iB_j
$$
离散沃尔什变换「DWT」
设 $DWT_i (A) = \sum\limits_{j = 0}^n A_jf(i, j)$ （第一次知道原来离散变换是这么设的）
又由于
$$
\begin{aligned}
DWT_i(A)DWT_i(B) &= DWT_i(C) \\
\sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j)f(i, k) &= \sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j \oplus k)
\end{aligned}
$$
故 $f(i, j)f(i, k) = f(i, j \oplus k)$
于是就有一些结论
- $and: f(i, j) = [(i and j) = i]$
- $or: f(i, j) = [(i and j) = j]$
- $xor: f(i, j) = (- 1)^{cnt (i and j)}$ （$cnt (x)$ 是 $x$ 的二进制位数）
至于证明自己意会一下就好了
又由于 $f(i, j)$ 满足二进制拆分，即
$$
f(i, j) = \prod\limits_{bit = 0}^{cntbit - 1} f(i_{bit}, j_{bit})
$$
那么将其左右拆分，推一下式子，得（注意下面的 $i_{bit}$ 表示的是从高到低的第 $bit$ 位）
$$
\begin{aligned}
DWT_i(A) &= \sum\limits_{j = 0}^n A_jf(i, j) \\
&= \sum\limits_{j = 0}^{\frac{n}{2} - 1} A_jf(i, j) + \sum\limits_{j = \frac{n}{2}}^{n - 1} A_jf(i, j)
\end{aligned}
$$
然后将它们的最高位提出来，得
$$
\begin{aligned}
DWT_i(A) = f(i_0, 0)\sum\limits_{j = 0}^{\frac{n}{2} - 1} A_j\prod_{bit = 1}^{cntbit - 1} f(i_{bit}, j_{bit}) + f(i_0, 1)\sum\limits_{j = \frac{n}{2}}^{n - 1}A_j\prod_{bit = 1}^{cntbit - 1} f(i_{bit}, j_{bit})
\end{aligned}
$$
整理一下，得 $(i \in [0, \frac{n}{2} - 1])$
$$
\begin{aligned}
DWT_i(A) &= f(0, 0)DWT_{\frac{n}{2}}(A_{left}) + f(0, 1)DWT_{\frac{n}{2}}(A_{right}) \\
DWT_{i + \frac{n}{2}}(A) &= f(1, 0))DWT_{\frac{n}{2}}(A_{left}) + f(1, 1)DWT_{\frac{n}{2}}(A_{right})
\end{aligned}
$$
至于 $iDWT$，就是解个二元一次方程的问题
接下来只要把 $FFT$ 的部分程序改一下就好了
下面记录一些常见公式
$$
and: a[i + j] += a[i + j + k] (DWT) \\
and: a[i + j] -= a[i + j + k] (iDWT) \\
\\
or: a[i + j + k] += a[i + j] (DWT) \\
or: a[i + j + k] -= a[i + j] (iDWT) \\
\\
xor: a[i + j] = a[i + j] + a[i + j + k], a[i + j + k] = a[i + j] - a[i + j + k] (DWT) \\
xor: a[i + j] = \frac{a[i + j] + a[i + j + k]}{2}, a[i + j + k] = \frac{a[i + j] - a[i + j + k]}{2} (iDWT)
$$