反演
反演，可以理解为两个事物通过某种关系的互相转化。
基本推论
设 \(F,G\)，满足 \(F(n) = \sum V[n,i]G(i)\)，其中 \(V\) 为矩阵，将 \(F,G\) 看成列向量，可以写做 \(F = V * G\)，那么我们可以容易推出 \(G = V^{-1} * F\)，这就是反演的过程，而一些特殊的反演即是利用了 \(V\)和\(V^{-1}\) 的特殊性。
也就是说，证明 \(A,B\) 互为反演关系，即证明 \(A * B = I\)。
单位根反演
设 \(\omega\) 为 \(n\)次单位根，则有
\[[a \equiv 0 \pmod n] = \frac{1}{n}\sum_{i = 0}^{n-1} \omega^{ia} \]证明
- 当 \(a = 0 \pmod n\) 时\[\frac{1}{n}\sum_{i = 0}^{n-1} \omega^{ia} = \frac{1}{n} \sum_{i = 0}^{n-1} \omega^{0} = 1 \]
- 当 \(a \neq 0 \pmod n\) 时
使用等比数列求和化简原式\[\frac{1}{n}\sum_{i = 0}^{n-1} \omega^{ia} = \frac{1}{n} * \frac{\omega^{na} - 1}{\omega^a - 1} \]其中 \(\omega^{na} - 1 = 0\)，而 \(\omega^a - 1 \neq 0\)，所以原式值为 \(0\)
从反演的视角看 \(\text{FFT}\)
设多项式 \(F,G\)，我们要求 \(H = F * G\)（循环卷积），可以易得
\[h_i = \sum_{x = 0}^n\sum_{y = 0}^n [x + y \equiv i \pmod n]f_xg_y \]\[h_i = \sum_{x = 0}^n\sum_{y = 0}^n [x + y - i \equiv 0 \pmod n]f_xg_y \]单位根反演一下得
\[h_i = \sum_{x = 0}^n\sum_{y = 0}^n \frac{1}{n}\sum_{k = 0}^{n -1}\omega^{(x + y - i)k}f_xg_y \]\[h_i = \frac{1}{n}\sum_{k = 0}^{n -1}\omega^{-ik}(\sum_{x=0}^nf_x\omega^{kx})(\sum_{y=0}^ng_y\omega^{ky}) \]\[h_i = \frac{1}{n}\sum_{k = 0}^{n -1}\omega^{-ik}F(\omega^k)G(\omega^k) \]这样我们就可以求出 \(F,G\) 在 \(\omega^0,...,w^{n-1}\) 上的点值来算出来 \(h_i\)，把求点值的过程写成矩阵
\[\begin{pmatrix} F(1) \\ F(\omega) \\ F(\omega^2) \\ \vdots \\ F(\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} f_0\\ f_1\\ f_2\\ \vdots\\ f_{n-1} \end{pmatrix}\]设关系矩阵为 \(A\)，其存在逆 \(A^{-1}_{i,j} = \frac{1}{n}\omega^{-ij}\)，我们惊奇地发现
\[\begin{pmatrix} h_0 \\ h_1 \\ h_2 \\ \vdots \\ h_{n-1} \end{pmatrix} =A^{-1}\times \begin{pmatrix} F(1)G(1)\\ F(\omega)G(\omega)\\ F(\omega^2)G(\omega^2)\\ \vdots\\ F(\omega^{n-1})G(\omega^{n-1}) \end{pmatrix}\]所以 \(H(\omega^k) = F(\omega^k)G(\omega^k)\)，而 \(\text{FFT}\) 的本质就是加速 \(A * F\) 和 \(A^{-1} * H\) 的过程。
\(\text{K - FWT}\)
这可以推广到高维，也就是 \(K\)进制 \(\text{FWT}\)，这里这论述异或卷积。
设 \(x, y\) 为两个列向量（\(m\)维），定义其加法为
其卷积为
\[h_i = \sum_{x = 0}^n\sum_{y = 0}^n [x + y = i]f_xg_y \]其中 \(i,x,y\) 均为列向量，代表一个状态。
相似的有结论
其中 \(x \cdot k\) 为向量的内积。
可以写出关系矩阵 \(A_{i,j} = \omega^{i \cdot j}\)，\(A^{-1}_{i,j} = \frac{1}{n}\omega^{-i\cdot j}\)
\(DFT\) 和 \(IDFT\) 的过程就是 \(A * F\) 和 \(A^{-1} * F\) 的过程。
高维 DFT 代码
void DFT(int *f, int len) {
for (int l = 1; l < len; l *= K)
for (int i = 0; i < len; i += l * K)
for (int j = i; j < i + l; j++) {
for (int x = 0; x < K; x++) b[x] = 0;
for (int x = 0; x < K; x++)
for (int y = 0; y < K; y++)
(b[x] += (LL)w[x * y % K] * f[j + y * l] % P) %= P;
for (int x = 0; x < K; x++) f[j + x * l] = b[x];
}
}