答案即为：
\(\displaystyle \sum_{i=0}^{n}{\binom{n}{i}p^i(1-p)^{n-i}i^k}\)
考虑化简：
\[\begin{aligned} \mathrm{Lemma1:}&i^k=\sum_{j}{\binom{i}{j}\begin{Bmatrix}k \\ j\end{Bmatrix}j!}\\ \mathrm{Lemma2:}&\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \end{aligned} \]\[\begin{aligned} &\sum_{i=0}^{n}{\binom{n}{i}p^i(1-p)^{n-i}i^k}\\ =&\sum_{i=0}^{n}{\binom{n}{i}p^i(1-p)^{n-i}}\sum_{j}{\binom{i}{j}\begin{Bmatrix}k \\ j\end{Bmatrix}j!}\\ =&\sum_{j}{\begin{Bmatrix}k \\ j\end{Bmatrix}j!}\sum_{i=0}^{n}{\binom{n}{i}\binom{i}{j}p^i(1-p)^{n-i}}\\ =&\sum_{j}{\begin{Bmatrix}k \\ j\end{Bmatrix}j!}\sum_{i=0}^{n}{\binom{n}{j}\binom{n-j}{i-j}p^i(1-p)^{n-i}}\\ =&\sum_{j}{\begin{Bmatrix}k \\ j\end{Bmatrix}\binom{n}{j}j!}\sum_{i=0}^{n}{\binom{n-j}{i-j}p^i(1-p)^{n-i}}\\ =&\sum_{j}{\begin{Bmatrix}k \\ j\end{Bmatrix}\binom{n}{j}j!}p^j\sum_{i=0}^{n}{\binom{n-j}{i-j}p^{i-j}(1-p)^{n-i}}\\ =&\sum_{j}{\begin{Bmatrix}k \\ j\end{Bmatrix}\binom{n}{j}j!p^j}\\ =&\sum_{j\le \min(k, n)}{\begin{Bmatrix}k \\ j\end{Bmatrix}\binom{n}{j}j!p^j} \end{aligned} \]化简到这里，已经可以用 \(O(k^2)\) 递推做掉这道题了。
然而还可以继续。
对 \(Lemma1\) 使用二项式反演得到：
\[\begin{aligned} i!\begin{Bmatrix}k \\ i\end{Bmatrix}=\sum_{j}{(-1)^{i-j}\binom{i}{j}j^k} \end{aligned} \]继续刚才的推导。
\[\begin{aligned} &=\sum_{j=0}^{\min(n,k)}{\binom{n}{j}p^j}\sum_{i=0}^{j}{(-1)^{j-i}\binom{j}{i}i^k}\\ &=\sum_{i=0}^{\min(n,k)}{i^k}\sum_{j=i}^{\min(n,k)}{\binom{j}{i}\binom{n}{j}(-1)^{j-i}p^j}\\ &=\sum_{i=0}^{\min(n,k)}{i^k(-1)^i\binom{n}{i}}\sum_{j=i}^{\min(n,k)}{\binom{n-i}{j-i}(-p)^j}\\ &=\sum_{i=0}^{\min(n,k)}{i^k\binom{n}{i}p^i}\sum_{j=0}^{\min(n,k)-i}{\binom{n-i}{j}(-p)^{j}} \end{aligned} \]考虑裂项求后面和式的递推式。
以下是 \(k\le n\) 的情况：
\[\begin{aligned} R_i&=\sum_{j=0}^{k-i}{\binom{n-i}{j}(-p)^j}\\ &=\sum_{j=0}^{k-i}{\binom{n-i-1}{j}(-p)^j}+\sum_{j=1}^{k-i}{\binom{n-i-1}{j-1}(-p)^j}\\ &=R_{i+1}+\binom{n-i-1}{k-i}(-p)^{k-i}+\sum_{j=0}^{k-i-1}{\binom{n-i-1}{j}(-p)^{j+1}}\\ &=R_{i+1}+\binom{n-i-1}{k-i}(-p)^{k-i}+(-p)\sum_{j=0}^{k-i-1}{\binom{n-i-1}{j}(-p)^{j}}\\ &=R_{i+1}-pR_{i+1}+\binom{n-i-1}{k-i}(-p)^{k-i}\\ \end{aligned} \]边界是 \(R_k=1\)
对于 \(n<k\) 的情况：\(R_i=(1-p)R_{i+1},R_n=1\)
综上所述：
\[\begin{aligned} Ans=\sum_{i=0}^{\min(n,k)}{i^k\binom{n}{i}p^iR_i} \end{aligned} \]半天没调出来，所以咕了一会。
标签：begin,end,sum,九月,二十五日,Bmatrix,binom,aligned,日记 From： https://www.cnblogs.com/mklzc/p/16731386.html