反演小记

佚名 / 2023-08-24 / 原文

反演

反演，可以理解为两个事物通过某种关系的互相转化。

基本推论

设 \(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\)维），定义其加法为

\[\begin{pmatrix} x_0\\ x_1\\ x_2\\ \vdots\\ x_{m-1} \end{pmatrix} + \begin{pmatrix} y_0\\ y_1\\ y_2\\ \vdots\\ y_{m-1} \end{pmatrix} = \begin{pmatrix} (x_0 + y_0) \bmod K\\ (x_1 + y_1) \bmod K\\ (x_2 + y_2) \bmod K\\ \vdots\\ (x_{m-1} + y_{m-1}) \bmod K\\ \end{pmatrix}\]

其卷积为

\[h_i = \sum_{x = 0}^n\sum_{y = 0}^n [x + y = i]f_xg_y \]

其中 \(i,x,y\) 均为列向量，代表一个状态。
相似的有结论

\[F(\omega^{k}) = \sum_x f_x\omega^{x \cdot k} \]

其中 \(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]; 
            }
}