简述
单位根反演（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} $$