【讲课笔记】FFT
没啥用的东西。
最近要给学弟讲课，稍微打点草稿，防止自己身败名裂。
root of unity
\[\exp\left(\frac{2k\pi i}{n}\right), k = 0, 1, \dots, n - 1\]
discrete Fourier transform
\[\operatorname{DFT}[g]_k = \sum_{t = 0}^{N - 1} g_t \cdot \omega_N^{tk}\]
convolution theorem
\[\begin{aligned} h_k = \sum_{i + j \equiv k \pmod N} f_i \cdot g_j \end{aligned}\]
\[\begin{aligned} N \cdot h_k &= \sum_i \sum_j f_i \cdot g_j \cdot [N \mid {i+j-k}] \cdot N\\ &=\sum_i \sum_j f_i \cdot g_j \sum_{t = 0}^{N - 1}\omega_N^{(i + j - k)t}\\ &=\sum_{t = 0}^{N - 1}\omega_N^{-tk}\left(\sum_i f_i\omega_N^{ti}\right)\cdot \left(\sum_j g_j\omega_N^{tj}\right)\\ &=\sum_{t = 0}^{N - 1}\omega_N^{-tk}\operatorname{DFT}[h]_t \end{aligned}\]
\[\operatorname{DFT}[h] = \operatorname{DFT}[f] \cdot \operatorname{DFT}[g]\]
Vandermonde matrix
\[\mathbf{F}=\begin{bmatrix} \omega_N^{0 \times 0} & \omega_N^{0 \times 1} & \cdots & \omega_N^{0 \times (N - 1)}\\ \omega_N^{1 \times 0} & \omega_N^{1 \times 1} & \cdots & \omega_N^{1 \times (N - 1)}\\ \vdots & \vdots & \ddots & \vdots\\ \omega_N^{(N - 1) \times 0} & \omega_N^{(N - 1) \times 1} & \cdots & \omega_N^{(N - 1) \times (N - 1)}\\ \end{bmatrix}\]
fast Fourier transform
\[\sum_{i = 0}^{N - 1}\frac{f_i}{1 - \omega_N^ix}\]
\[\sum_{i = 0}^{N - 1}(1 - \omega_N^ix) = 1 - x^N\]
考虑类似分治 FFT 的过程。
对于分治右边调整奇偶：
\[\frac{F(x)}{1 - x^N} \Rightarrow \frac{F(x\omega_{2N})}{1 + x^N}\]
decimation in time and decimation in frequency
binomial inversion
\[\sum_{i=0}^n\binom{n}{i}(-1)^i=[n=0]\]
fast Walsh–Hadamard transform
对每一维做大小为 \(2\) 的单位根反演。
\[\operatorname{sgn}(i, j) = (-1)^{\operatorname{popcount}(i \operatorname{and} j)}\]
\[\mathcal{F}_i = \operatorname{FWT}(F)_i = \sum F_j \cdot \operatorname{sgn}(i, j)\]
\[\begin{aligned} \mathcal{H}_b &= \sum_i \sum_j f_i \cdot g_j \cdot \operatorname{sgn}(i \oplus j, b)\\ &= \sum_i \sum_j f_i \cdot g_j \cdot \operatorname{sgn}(i, b) \cdot \operatorname{sgn}(j, b)\\ &= \left(\sum_i f_i \cdot \operatorname{sgn}(i, b)\right) \left(\sum_j g_j \cdot \operatorname{sgn}(j, b)\right)\\ &= \mathcal{F}_b \cdot \mathcal{G}_b \end{aligned}\]
\[\begin{aligned} h_k &= \sum_{i \oplus j = k}f_i \cdot g_j\\ &= \sum_i \sum_j f_i \cdot g_j \cdot [2 \mid {i_0 + j_0 - k_0}] \cdot [2 \mid {i_1 + j_1 - k_1}] \cdots\\ &= \frac{1}{2^w}\sum_i \sum_j f_i \cdot g_j \cdot (1 + (-1)^{i_0 + j_0 - k_0}) \cdot (1 + (-1)^{i_1 + j_1 - k_1})\\ &= \frac{1}{2^w}\sum_i \sum_j f_i \cdot g_j \cdot \sum_b (-1)^{i_0 \operatorname{and} b_0} \cdot (-1)^{j_0 \operatorname{and} b_0} \cdot (-1)^{k_0 \operatorname{and} b_0} \cdot (-1)^{i_1 \operatorname{and} b_1} \cdot (-1)^{j_1 \operatorname{and} b_1} \cdot (-1)^{k_1 \operatorname{and} b_1} \cdots\\ &= \frac{1}{2^w}\sum_b \operatorname{sgn}(k, b) \cdot (\sum_i f_i \cdot \operatorname{sgn}(i, b)) \cdot (\sum_j g_j \cdot \operatorname{sgn}(j, b))\\ &= \frac{1}{2^w}\sum_b \operatorname{sgn}(k, b) \cdot \mathcal{F}_b \cdot \mathcal{G}_b\\ &= \frac{1}{2^w}\sum_b \operatorname{sgn}(k, b) \cdot \mathcal{H}_b\\ &= \frac{1}{2^w}\operatorname{FWT}(\mathcal{H})_k \end{aligned}\]