\(\mathcal{Preface}\)

单位根反演，顾名思义就是用单位根变换一类式子的形式。有关单位根的基本概念可见我的这篇博客。

\(\mathcal{Formula}\)

单位根反演的公式很简单：

[[k|n]=\frac{1}k\sum_{i=0}^{k-1}\omega_k^{ni} ]

\(\mathcal{Proof}\)

分类讨论：

1. \(k|n\). 那么 \((\forall i)(\omega_k^{ni}=1)\)，所以右侧为 \(\frac{1}k\sum_{i=0}^{k-1}1=1\)。

2. \(k\not=n\). 等比数列求和，右侧为 \(\frac{1}k\cdot\frac{1-\omega_k^{kn}}{1-\omega_k^n}\)，其中 \(\omega_k^{kn}=1\)，故分子为 \(0\)，分母不为 \(0\)，式子的值为 \(0\)。

   综上，得证。

\(\mathcal{Inference}\)

实际问题中，我们往往需要求出对于某个多项式（多为生成函数）\(f\) 的特定倍数次数的系数和。即求：

[\sum_{i=0}^{\lfloor \frac{n}k\rfloor}[x^{ik}]f(x) ]

运用单位根反演的基本公式变形：

[\begin{aligned} \sum{i=0}^{\lfloor\frac{n}k\rfloor}[x^{ik}]f(x)&=\sum{i=0}^n[k|i][x^i]f(x)\ &=\sum{i=0}^n[x^i]f(x)\cdot\frac{1}k\sum{j=0}^{k-1}\omegak^{ij}\ &=\frac{1}k\sum{j=0}^{k-1}\sum_{i=0}^n[x^i]f(x)(\omegak^j)^i\ &=\frac{1}k\sum{j=0}^{k-1}f(\omega_k^j) \end{aligned} ]

只要能快速求出 \(f\) 在所有 \(k\) 次单位根处的点值，就能 \(\mathcal O(k)\) 得出原式的值啦。

更方便的形式，若我们想求 \(i\bmod k=r\) 时 \([x^i]f(x)\) 之和，只需要在运用反演时移动一下 \(\omega_k\) 的指标：

[\begin{aligned} \sum{i=0}^n[i\bmod k=r][x^i]f(x)&=\frac{1}k\sum{i=0}^n\left(\sum_{j=0}^{k-1}\omegak^{j(i-r)} \right)[x^i]f(x)\ &=\frac{1}k\sum{j=0}^{k-1}\omega_{k}^{-jr}f(\omega_k^j) \end{aligned} ]

当然，我们常用原根代替单位根。

\(\mathcal{Examples}\)

「LOJ 6485」 LJJ 学二项式定理 & my solution.