一个非常不阳间的关于单位根的性质:
\[\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) \]例题:
BZOJ3328 PYXFIB (矩形上的单位根反演模板)
标签:frac,sum,单位根,反演,Ans,omega From: https://www.cnblogs.com/oier-moonlit/p/17610922.html