伞兵看错题了好久 /hanx，我还以为是第一次出现王牌的轮数期望值的 \(k\) 次方。

一个直观的做法就是考虑 \(i^k\) 的组合意义：相当于从那些出现王牌的轮次中可重带标号地选择 \(k\) 轮，注意到只需要管被选到的最多 \(k\) 轮，设计一个 dp 解决即可。

接下来考虑加强版，枚举出现王牌的次数，列出答案式：

\[\begin{aligned} &\sum_{i=0}^{n}i^k{n\choose i}\left(\frac{1}{m}\right)^i\left(1-\frac{1}{m}\right)^{n-i}\\ &=\sum_{i=0}^{n}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix} n^{\underline{j}}{n-j\choose n-i}\left(\frac{1}{m}\right)^i\left(1-\frac{1}{m}\right)^{n-i}\\ &=\sum_{j=0}^{k}\left(\frac{1}{m}\right)^{j}\begin{Bmatrix}k\\ j\end{Bmatrix}n^{\underline{j}}\\ &=\sum_{j=0}^{k}\left(\frac{1}{m}\right)^{j}n^{\underline{j}}\frac{1}{j!}\sum_{i=0}^{j}(-1)^{j-i}{j\choose i}i^k\\ &=\sum_{i=0}^{k}i^k(-1)^{i}{n\choose i}\sum_{j=i}^{k}{n-i\choose n-j}\left(\frac{1}{m}\right)^{j}(-1)^{j}\\ \end{aligned} \]

关键在于后面那一块：

\[\begin{aligned} f(i)&=\sum_{j=i}^{k}{n-i\choose n-j}\left(\frac{1}{m}\right)^{j}(-1)^{j}\\ &=f(i+1)+\sum_{j=i}^{k}{n-i-1\choose n-j-1}\left(\frac{1}{m}\right)^{j}(-1)^{j}\\ &=f(i+1)-m\left(f(i+1)+{n-i-1\choose n-k-1}\left(\frac{1}{m}\right)^{k+1}(-1)^{k+1}\right)\\ \end{aligned} \]

然后就可以递推了，中间稍微处理一下 \((n-i-1)^{\underline{k-i}}\) 就行。

代码：Submission #130442979 - Codeforces