单位根反演

最基础的用途是用于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!}$

通过单位根反演转化为

$ \begin{aligned}\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}\end{aligned}$

作为无穷级数压缩的一种方法

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

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