\[ [n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_{n}^{ik} \]
证明：
首先根据单位根的性质 \(\omega_{n}^{kn} = 1\) ，所以当 \(n |k\) 时每一项都等于 \(1\)，有 \(\frac{1}{n}\sum_{i=0}^{n-1} \omega_{n}^{ik} = 1\) 。
当 \(n|k\) 不成立时，\(\omega_{n}^k\neq 1\) ，等比数列求和得
\[
\frac{1}{n}\sum_{i=0}^{n-1}\omega_{n}^{ik}=\frac{1}{n}\times\frac{1-\omega_{n}^{nk}}{1-\omega_{n}^k}
\]
又因为 \(\omega_{n}^{nk}=1\) ，所以上式为 \(0\) ，得证。
有一个长度为 \(n\) 的序列，有 \(m\) 种颜色，要求给这个序列染完色之后，每一种颜色的出现次数都能被 \(d\) 整除，求合法的染色方案数。
相当于是集合拼接并去掉集合拼接顺序的影响，直接上 EGF，我们即要求
\[
[x^n](\sum_{i =0}^n [d|i]\frac{x^i}{i!})^m
\]
原式等价于 \([x^n]e^{mx}\) ，第 \(n\) 项的系数就是 \(m^n\) ，其实这个直接就能得到了，小学生计数。
这里也不用上单位根反演，直接二项式定理展开就好了，类似与 CTS2019 珍珠其中一步的推法。
\[
\begin{align}
[x^n](\sum_{i =0}^n [d|i]\frac{x^i}{i!})^m &= [x^n](\frac{e^{x}+e^{-x}}{2})^m \ &=[x^n]\frac{1}{2^m}\sum_{i=0}^m {m \choose i}e^{(2i-m)x} \ &=\frac{1}{2^m}\sum_{i=0}^m {m \choose i}(2i-m)^n
\end{align}
\]
前面为什么不上单位根反演是有深层次道理的
\[
\begin{align}
[x^n](\sum_{i =0}^n [d|i]\frac{x^i}{i!})^m &= [x^n](\sum_{i=0}^n(\frac{1}{d}\sum_{j=0}^{d-1}\omega_{d}^{ij})\frac{x^i}{i!})^m \\ &= [x^n]\frac{1}{d^m}(\sum_{j=0}^{d-1}\sum_{i=0}^n\frac{(x\omega_d^j)^i}{i!})^m \&= [x^n]\frac{1}{d^m}(\sum_{j=0}^{d-1}e^{x\omega_{d}^j})^m \&=\frac{1}{3^m}\sum_{i+j+k=m}\frac{m!}{i!j!k!}[x^n](e^{ix\omega_{d}^0+jx\omega_{d}^1+kx\omega_{d}^2}) \&=\frac{1}{3^m}\sum_{i+j+k=m}\frac{m!}{i!j!k!}(i\omega_{d}^0+j\omega_{d}^1+k\omega_{d}^2)^n
\end{align}
\]
因为这里单位根反演复杂度是 \(\mathcal O(k^{d-1})\)
原文：https://www.cnblogs.com/mangoyang/p/11723825.html