单位根反演

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

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

式子非常简单：

$\sum _{j=0}^{n-1}{\omega }_n^{ij}=\{\begin{array}{rlr}\frac{{\omega }_n^{in}-1}{{\omega }_n^i-1}=0& & i\ne 0\\ n& & i=0\end{array}$。

更简洁的式子为 $\begin{array}{r}\frac{\sum _{j=0}^{n-1}{\omega }_n^{ij}}{n}=[n|i]\end{array}$。

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

如 $\sum _{n|i}\frac{x^i}{i!}$。

通过单位根反演转化为：

$$\sum _{n|i}\frac{x^i}{i!}=\sum _{i=0}^{\mathrm{\infty }}\frac{\sum _{j=0}^{n-1}{\omega }_n^{ij}}{n}\cdot \frac{x^i}{i!}=\sum _{i=0}^{\mathrm{\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$ 阶单位根。。。