前言
很久以前就听说是个挺有用的东西，然而一直没有去学。
最近打算恶补一下数学，像类欧啊，单位根反演啊，斯特林反演啊，都决定去写篇博客装装样子、充充门面。
于是，我来了。
大致用途
在(O(k))的时间内求出一个数列中所有下标为(k)的倍数的数值和。
当然，它也同样可以应用于生成函数中发挥神奇的作用。
公式
[[k|n]=frac 1ksum_{i=0}^{k-1}omega_k^{ni}
]
开局上公式的操作让我不禁想到拉格朗日插值。
考虑如何证明，自然是分两类讨论。
当(k|n)时：
[frac1ksum_{i=0}^{k-1}omega_k^{ni}=frac1ksum_{i=0}^{k-1}(omega_k^n)^i=frac 1k imes k=1
]
当(k ot|n)时：
[frac1ksum_{i=0}^{k-1}omega_k^{ni}=frac 1kcdot omega_k^0cdotfrac{omega_k^0-omega_k^{kn}}{1-omega_k^n}=frac 1kcdot omega_k^0cdot 0=0
]
证明完毕。
这篇博客就是当个摆设的，例题什么的看情况再补吧。