需要注意题目求解的是操作 $n$ 次出现 $x$ 次王牌，而不是第一次出现王牌是第 $x$ 次。

令 $p=\frac{1}{m}$ 也就选出王牌的概率，$q=1-p$。

那么如果直接枚举出现王牌的数量，有式子：

$\sum\limits_{i=0}^n {n\choose i}p^iq^{n-i}i^k$

根据套路把 $i^k$ 展开为第二类斯特林数：

$\sum\limits_{i=0}^n {n\choose i}p^iq^{n-i}i^k=\sum\limits_{i=0}^n{n\choose i}p^iq^{n-i}\sum_{j=1}^k\begin{Bmatrix}k\\ j\end{Bmatrix}\frac{i!}{(i-j)!}$

因为我们希望最后的时间复杂度与 $n$ 无关，先把与 $n$ 有关的式子移动到外面：

$\sum\limits_{i=0}^n {n\choose i}p^iq^{n-i}i^k=\sum\limits_{j=1}^k\begin{Bmatrix}k\\ j\end{Bmatrix}\sum\limits_{i=0}^n {n\choose i}p^iq^{n-i}\frac{i!}{(i-j)!}$

考虑把后面的一坨式子化简，阶乘一般的处理手段都是加入组合数然后根据组合数的性质快速计算。

$\sum\limits_{i=0}^n {n\choose i}p^iq^{n-i}\frac{i!}{(i-j)!}=\sum\limits_{i=0}^n \frac{n!}{i!(n-i)!}\times \frac{i!}{(i-j)!}p^iq^{n-i}$

因为阶乘很狗屎，所以先处理阶乘。

$\sum\limits_{i=0}^n {n-i\choose i-j}\frac{n!}{(n-j)!}p^iq^{n-i}$

把式子分开看：

$\frac{n!}{(n-j)!}\sum\limits_{i=0}^{n-j} {n-i\choose i}p^{i+j}(1-p)^{n-i-j}$

这里需要补一下二项式定理：

$(a+b)^n=\sum\limits_{i=0}^n {n\choose i}a^{i}b^{n-i}$

发现跟上面的式子有点像，考虑把 $p^i$ 提出来，得到：

$\frac{n!}{(n-j)!}p^j(p+(1-p))^{n-i}=\frac{n!}{(n-j)!}\times p^j$

将化简之后的结果带回原式，得到：

$\sum\limits_{j=0}^k \begin{Bmatrix}k\\ j\end{Bmatrix}\frac{n!}{(n-j)!}p^j$

虽然是垃圾的 $O(k\log n)$，但是你就说能不能过吧。