单位根反演
就是下面这个式子：
\[[n|k]=\frac{1}{n}\sum_{i=0}^{n-1} w_n^{ik} \]证明：
- 当 \(n|k\) 时，\(w_n^{ik}=1\)，原式成立。
- 当 \(n\not{|}k\) 时，原式等于 \(\frac{1}{n}\cdot \frac{1-w^{nk}}{1-w^k}=0\)。
应用
求一个多项式 \(f(x)\) 次数为 \(d\) 的倍数的系数和，其中需满足存在 \(d\) 次单位根 \(w_{d}\)。
设 \(f(x)=\sum_{i=0}^n a_ix^i\)，那么：
\[\begin{aligned} &\sum_{i=0}^n [d|i]a_i\\ =&\sum_{i=0}^na_i\frac{1}{d}\sum_{j=0}^{d-1}w_d^{ij}\\ =&\frac{1}{d}\sum_{j=0}^{d-1}\sum_{i=0}^na_iw_d^{ij}\\ =&\frac{1}{d}\sum_{j=0}^{d-1}f(w_{d}^j) \end{aligned} \]于是如果求 \(f(x)\) 的时间复杂度为 \(O(t)\)，那么就能在 \(O(dt)\) 的时间复杂度内解决这个问题。
所以一般应用于 \(d\) 为较小的定值，以及 \(f(x)\) 有良好的实际意义（能快速求）的情况。
当然把条件变成模 \(d\) 余 \(r\) 也是可以的，只需要将多项式平移即可。
把多项式换成数列也是可以的，只需要把数列换成其生成函数。
标签：frac,多项式,sum,单位根,反演,复杂度 From： https://www.cnblogs.com/ez-lcw/p/16843068.html