单位根反演

命题如下：

$$
\forall k\in Z,[n|k]=\frac{1}{n}\sum\limits_{i=0}^{{n-1}\omega_n}
$$

证明：

设 $[n|k]=1$，则根据单位根性质，我们可以得到：

$$
\sum\limits_{i=0}^{{n-1}\omega_n}=n
$$

设 $[n|k]=0$，则：

$$
\sum\limits_{i=0}^{{n-1}\omega_n}=\frac{\omega_n^{{nk}-1}{\omega_n}-1}=0
$$

由此可知式子成立。

由此可知，如果想要知道一个多项式特定倍数次项的系数之和，就可以这么做：

$$
\begin{aligned}
\sum\limits_{i=0}^{\left\lfloor \frac nk \right\rfloor}[x^{{ik}]f(x)&=\sum\limits_{i=0}}n[k|i][x^i]f(x)\
&=\sum\limits_{i=0}^n [x^i]f(x)\frac 1k\sum\limits_{j=0}^{{k-1}\omega_k}=\frac 1k \sum\limits_{i=0}^{na_i\sum\limits_{j=0}}\omega_n^{ji}\
&=\frac 1k \sum\limits_{j=0}^{{k-1}\sum\limits_{i=0}}na_i(\omega_n^{j})i=\frac 1k \sum\limits_{j=0}^{{k-1}f(\omega_n}j)
\end{aligned}
$$

一个推论

$$
[a=b]=\frac 1n \sum\limits_{i=0}^{{n-1}\omega_n}(a,b<n)
$$

证明是显然的。