题解 P5591 【小猪佩奇学数学】

foreverlasting

2019-10-13 14:52:13

Solution

[并没有同步发在这里,只是单纯的推销一下](https://foreverlasting1202.github.io/) 单位根反演。 好像我的做法极其垃圾,反正能过就好了。 $\sum_{i=0}^n \binom{n}{i}p^i\lfloor{\frac{i}{k}}\rfloor$ $=\sum_{i=0}^n \binom{n}{i}p^i\frac{i-i\ mod\ k}{k}$ $=\frac{1}{k}\sum_{i=0}^n \binom{n}{i}p^i(i-i\ mod\ k)$ $=\frac{1}{k}(\sum_{i=0}^n i\binom{n}{i}p^i-\sum_{i=0}^n (i\ mod\ k)\binom{n}{i}p^i)$ $\sum_{i=0}^n (i\ mod\ k)\binom{n}{i}p^i$ $=\sum_{d=0}^{k-1}d\sum_{i=0}^n [i\ mod\ k==d]\binom{n}{i}p^i$ $\sum_{i=0}^n [i\ mod\ k==0]\binom{n}{i}p^i$ $=\sum_{i=0}^n\frac{1}{k}\sum_{j=0}^{k-1}\omega^{ij}_k\binom{n}{i}p^i$ $=\sum_{i=0}^n\frac{1}{k}\sum_{j=0}^{k-1}\binom{n}{i}(p\omega^{j}_k)^i$ $=\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^n\binom{n}{i}(p\omega^{j}_k)^i$ $=\frac{1}{k}\sum_{j=0}^{k-1}(1+p\omega^{j}_k)^n$ $\sum_{d=0}^{k-1}d\sum_{i=0}^n [i\ mod\ k==d]\binom{n}{i}p^i$ $=\frac{1}{k}\sum_{d=0}^{k-1}d\sum_{j=0}^{k-1}(1+p\omega^{j}_k)^n\frac{1}{(\omega^j_k)^d}$ $=\frac{1}{k}\sum_{j=0}^{k-1}(1+p\omega^{j}_k)^n\sum_{d=0}^{k-1}d\frac{1}{(\omega^j_k)^d}$ 然后后面那个东西是个简单的等差等比数列求和,于是随便做做就能过了。$O(klogn)$。