再探 FFT&FWT：从单位根反演出发
设 \(\omega\) 为 \(n\) 次单位根。有如下性质：
\[\frac 1n\sum_{k = 0} ^ {n - 1} \omega ^ {vk} = [v \bmod n = 0]
\]
套路大概是看到 \([n | v]\) 这类式子直接化成单位根的形式。
考虑如何计算两个序列的循环卷积：
\[\begin{align*}
c_r &= \sum_{p=0}^{n-1} \sum_{q=0}^{n-1} [p + q \equiv r \pmod n] a_pb_q \\
&= \sum_{p=0}^{n-1} \sum_{q=0}^{n-1} [p + q - r \equiv 0 \pmod n] a_pb_q \\
&= \frac1n\sum_{p=0}^{n-1} \sum_{q=0}^{n-1} \sum_{k=0}^{n-1} \omega^{-rk} \cdot \omega^{pk} \cdot \omega^{pk} a_pb_q\\
&= \frac1n\sum_{k=0}^{n-1} \omega^{-rk} (\sum_{p=0}^{n-1} \omega^{pk} a_p)(\sum_{q=0}^{n-1}\omega^{qk} b_q)
\end{align*}
\]
设 \(A(x) = \sum_{k=0}^{n-1}a_kx^k\)，\(B(x)\)，\(C(x)\) 同理，则有
\[c_r = \frac1n\sum_{k=0}^{n-1}\omega^{-rk}A(\omega^k)B(\omega^{rk})\\
A(\omega^k) = \sum_{j=0}^{n-1}\omega^{jk}a_j
\]
故只需求出 \(A(x)\) 在 \(1,\omega,\omega^2 \cdots\omega^{n-1}\) 处的点值再用类似的方法求出 \(c\) 即可，具体做法不再阐述。这就是 FFT。
这里还有更加美妙的性质，我们用范德蒙矩阵的形式来描述上面求点值的过程。
\[\begin{pmatrix}
A(1) \\
A(\omega) \\
A(\omega^2) \\
\vdots \\
A(\omega^{n-1})
\end{pmatrix} =
\begin{pmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\
1 & \omega^2 & \omega^{2 \times 2} & \cdots & \omega^{2 \times (n-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega^{n - 1} & \omega^{(n - 1) \times 2} & \cdots & \omega^{(n-1) \times (n - 1)}
\end{pmatrix} \times
\begin{pmatrix}
a_0\\
a_1\\
a_2\\
\vdots\\
a_{n-1}
\end{pmatrix}
\]
转移矩阵\(\mathbf{V}_{ij} = \omega^{i j}\)，这个矩阵叫做傅里叶矩阵，它存在逆元 \(\mathbf{V}^{-1}_{ij} = \frac1n\omega^{-ij}\)。\(\mathbf{V}^{-1}\) 恰好描述了我们上面反解出 \(c\) 的过程。
于是我们得到这个简洁而优美的式子：
\[C(\omega^{k}) = A(\omega^k) \cdot B(\omega^k)
\]
故 FFT 的本质其实就是快速求出已知多项式的点值，然后利用傅里叶矩阵的特性快速插值回去。
接下来来看 FWT。
定义 \(m\) 维向量的不进位加法
\[\begin{pmatrix}
A_0\\
A_1\\
A_2\\
\vdots\\
A_{m-1}
\end{pmatrix} +
\begin{pmatrix}
B_0\\
B_1\\
B_2\\
\vdots\\
B_{m-1}
\end{pmatrix} =
\begin{pmatrix}
(A_0 + B_0) \bmod k\\
(A_1 + B_1) \bmod k\\
(A_2 + B_2) \bmod k\\
\vdots\\
(A_{m-1} + B_{m-1}) \bmod k\\
\end{pmatrix}
\]
求下标为 \(m\) 维向量的两序列在上述加法意义下的卷积：
\[c_r = \sum_{p} \sum_{q} [p + q = r] a_pb_q
\]
对每一维做 FFT 即可，具体来说
\[A_u = \sum_v \omega ^{u \cdot v} a_v
\]
其中 \(\omega\) 是 \(k\) 次单位根，\(u \cdot v\) 是向量的不进位内积。注意到这里其实用了 \((p+q) \cdot k = p \cdot k + q \cdot k\) 这一性质，即内积对加法的分配律。
故 FWT 本质上就是 FFT 的高维推广。
总结：厉害了我的哥！
参考资料：
- 2016年国家集训队论文毛啸《再探快速傅里叶变换》
- 线性代数系列（十七）--复数矩阵和傅里叶矩阵