单位根反演

· · 个人记录

简述

单位根反演（unit-root-inversion），是一种将原式通过转换为一些带有单位根的式子，然后通过单位根的性质计算的方法。

公式

\left[d \mid n\right] = \frac1d\sum\limits_{i = 0}^{d - 1}\omega_d^{ni}

证明

当 d \mid n 时，上述式子显然成立。

否则，根据等比数列求和公式可以得到

\frac1d\sum\limits_{i = 0}^{d - 1}\omega_d^{ni} = \frac{1 - \omega_d^{dn}}{1 - \omega_d^n} = 0

数论拓展

目前我们需要单位根的性质仅有：仅有 \omega_d^{dk} = 1，其他都不为 1，其中 k 是整数。可以考虑在模 p 意义下找到阶为 k 的数来代替单位根。

生成函数拓展

若 F\left(x\right) = \sum\limits_{i = 0}^n a_ix_i。我们想求 G\left(x\right) = \sum\limits_{i = 0}^n a_i\left[d \mid i\right]。

\begin{aligned} G\left(x\right) &= \sum\limits_{i = 0}^n a_i\left[d \mid i\right] \\ &= \sum\limits_{i = 0}^n a_i\left(\frac1d\sum\limits_{j = 0}^{d - 1}\omega_d^{ij}\right) \\ &= \frac1d\sum\limits_{j = 0}^{d - 1}\left(\sum\limits_{i = 0}^n a_i\omega_d^{ji}\right) \\ &= \frac1d\sum\limits_{j = 0}^{d - 1}F\left(\omega_d^{j}\right) \end{aligned}

应用

组合数求和：

\sum\limits_{i = 0}^n\binom{kn}{ki}

开始单位根反演之前，我们有一个玩意，单位根反演会用到：

\sum\limits_{i = 0}^n\binom nix^i = \left(1 + x\right)^n

然后我们可以开始单位根反演了。

\begin{aligned} \sum\limits_{i = 0}^n\binom{kn}{ki} &= \sum\limits_{i = 0}^{kn}\binom{kn}i\left[k \mid i\right] \\ &= \frac1k\sum\limits_{j = 0}^{k - 1}\left(\sum\limits_{i = 0}^{kn}\binom{kn}i\omega_k^{ji}\right) \\ &= \frac1k\sum\limits_{j = 0}^{k - 1}\left(1 + \omega_k^j\right)^{kn} \end{aligned}