题目链接：洛谷
\[ Ans=\frac{1}{k}(\sum_{i=0}^n\binom{n}{i}p^ii-\sum_{i=0}^n\binom{n}{i}p^i(i \ \mathrm{mod} \ k)) \]
\[ \begin{aligned} Ans&=\sum_{i=0}^n\binom{n}{i}p^i(i \ \mathrm{mod} \ k) \&=\sum_{d=0}^{k-1}\sum_{i=0}^n\binom{n}{i}p^id((i-d) \ \mathrm{mod} \ k=0) \&=\frac{1}{k}\sum_{d=0}^{k-1}\sum_{i=0}^n\binom{n}{i}p^id\sum_{j=0}^{k-1}w_k^{(i-d)j} \&=\frac{1}{k}\sum_{d=0}^{k-1}d\sum_{j=0}^{k-1}w_k^{-dj}\sum_{i=0}^n\binom{n}{i}(pw_k^{j})^i \&=\frac{1}{k}\sum_{d=0}^{k-1}d\sum_{j=0}^{k-1}w_k^{-dj}(pw_k^j+1)^n \&=\frac{1}{k}\sum_{i=0}^{k-1}(pw_k^i+1)^n\sum_{d=0}^{k-1}d(w_k^{-i})^d \end{aligned} \]
现在推推后面一部分。
\[
\begin{aligned}
S&=\sum_{i=0}^{k-1}ix^i \&=\sum_{i=0}^{k-1}(i+1)x^{i+1}-kx^k \&=x\sum_{i=0}^{k-1}ix^i+\sum_{i=0}^{k-1}x^i-kx^k \&=xS+\frac{1-x^k}{1-x}-kx^k \(1-x)S&=\frac{1-x^k}{1-x}-kx^k \\because x^k&=1\S&=\frac{k}{1-x} \Ans&=\frac{(p+1)^n(k-1)}{2}+\sum_{i=1}^{k-1}\frac{(pw_k^i+1)^n}{1-w_k^{-i}}
\end{aligned}
\]
还有一部分
\[
\begin{aligned}
Ans&=\sum_{i=0}^n\binom{n}{i}p^ii \&=np\sum_{i=0}^{n-1}\binom{n-1}{i}p^i \&=np(p+1)^{n-1}
\end{aligned}
\]
原文：https://www.cnblogs.com/AThousandMoons/p/11697920.html