单位根反演

最基础的用途是用于 FFT 中点值式转多项式。

即对于 \(G(i)=F(\omega_n^i)\) ，由 \(G(i)\) 反演得到 \([x^i]F(i)\) 的过程，称之为单位根反演。

式子非常简单：

\(\sum_{j=0}^{n-1}\omega_n^{ij}= \left\{\begin{aligned} \frac{\omega_n^{in}-1}{\omega_n^i-1}=0 && i\ne 0\\ n && i=0\end{aligned} \right.\)。

更简洁的式子为 \(\begin{aligned}\frac{\sum_{j=0}^{n-1}\omega_n^{ij}}{n}=[n|i]\end{aligned}\)。

在生成函数的化简与构造中，常用于解决 \(\mod n=0\) 的限制。

如 \(\sum_{n|i}\frac{x^i}{i!}\)。

通过单位根反演转化为：

\[ \sum_{n|i}\frac{x^i}{i!}=\sum_{i=0}^{\infty}\frac{\sum_{j=0}^{n-1}\omega_n^{ij}}{n} \cdot \frac{x^i}{i!}=\sum_{i=0}^{\infty}\sum_{j=0}^{n-1} \frac{(x\omega_n^j)^i}{i!}=\sum_{j=0}^{n-1}e^{x\omega_n^j} \] 作为无穷级数压缩的一种方法。

但是单位根反演转化有一个非常明显的局限，就是在模意义下， \(n\) 阶单位根很可能无法求解。

现在笔者还不会求模意义下特定的 \(n\) 阶单位根。。。