题解

思路

$x$ 服从参数为 $n$ 和 $p=1/m$ 的二项分布。小范围可以枚举每次是否抽中；中等范围可以直接枚举二项分布的取值；当 $n$ 很大时，改用下降幂矩。

做法

普通幂可以用第二类 Stirling 数展开：

二项分布的第 $j$ 阶下降幂矩为

因此答案为

使用递推 $S(i,j)=S(i-1,j-1)+jS(i-1,j)$ 逐行计算到第 $k$ 行。随后同步维护 $n$ 的下降幂和 $m^{-1}$ 的幂并求和。

中等规模的直接二项分布算法从 $P(x=0)=(1-p)^n$ 出发，用相邻概率比递推 $P(x+1)$，再累加 $x^kP(x)$。

复杂度

满分算法时间复杂度为 $O(k^2)$，空间复杂度为 $O(k)$。