单位根反演

标签：frac sum 单位根 反演 Ans omega

一个非常不阳间的关于单位根的性质：

\[\forall k,[n∣k]=\frac{1}{n}\sum _{i=0}^{n−1}\omega^{ik}_{n} \]

证明：

若 \(n∣k\)，则有

\[Ans=\frac{1}{n}\sum _{i=0}^{n−1}ω^{ink^′}_n=\frac{1}{n}\sum_{i=0}^{n−1}1=1 \]

否则，等比数列求和有

\[Ans=\frac1n\frac{ω^0_n−ω^{nk}_n}{1−ω^k_n}=0 \]

应用：

设：

\[f(x)=\sum_{i=0}^{n}a_ix^i \]

则

\[\sum_{i=0}^{n}a_{i}x^{i}[k|i]=\sum_{i=0}^{n}a_i \frac{1}{k}\sum_{j=0}^{k-1}(\omega_{k}^{j})^{i}=\frac{1}{k}\sum_{j=0}^{k-1}f(\omega_k^j) \]

例题：

[LOJ 6485] LJJ 学二项式定理 （模板）

BZOJ3328 PYXFIB （矩形上的单位根反演模板）

标签：frac,sum,单位根,反演,Ans,omega
From： https://www.cnblogs.com/oier-moonlit/p/17610922.html