题解

思路

设一次“轮次”为一次洗牌后不断抽牌，直到抽到下一张小丑牌为止。每一轮结束后牌堆恢复原状并重新随机排列，因此各轮的随机结果独立同分布。

记 $X$ 为一轮消耗的秒数，$N$ 为收集完全部数字牌时经历的轮数。总时间为前 $N$ 轮长度之和。

一轮的期望长度

固定一张数字牌。只看它与 $m$ 张小丑牌的相对次序，它在本轮被抽到，当且仅当它排在所有小丑牌之前。这个事件的概率为

$$\frac{1}{m+1}.$$

由期望的线性性，一轮抽到的数字牌数期望为 $\frac{n}{m+1}$。本轮还一定会抽到作为终止标志的一张小丑牌，所以

$$\mathbb E[X]=1+\frac{n}{m+1}=\frac{n+m+1}{m+1}.$$

需要的轮数

考虑任意一个由 $k$ 张指定数字牌组成的集合 $A$。一轮完全没有抽到 $A$ 中的牌，等价于在这 $k$ 张牌和 $m$ 张小丑牌中最先出现的是小丑牌，因此概率为

$$\frac{m}{m+k}.$$

经过 $r$ 轮后，$A$ 中所有牌仍未出现的概率为 $\left(\frac{m}{m+k}\right)^r$。对“至少有一张数字牌尚未收集”使用容斥，并利用非负整数随机变量的尾和公式，可得

$$\begin{aligned} \mathbb E[N] &=\sum_{r\ge 0}\Pr(N>r)\\ &=\sum_{k=1}^{n}(-1)^{k+1}\binom nk \sum_{r\ge0}\left(\frac{m}{m+k}\right)^r\\ &=\sum_{k=1}^{n}(-1)^{k+1}\binom nk\frac{m+k}{k}. \end{aligned}$$

使用两个经典容斥恒等式

$$\sum_{k=1}^{n}(-1)^{k+1}\binom nk=1, \qquad \sum_{k=1}^{n}(-1)^{k+1}\binom nk\frac1k=H_n,$$

其中 $H_n=\sum_{i=1}^{n}\frac1i$ 为第 $n$ 个调和数，于是

$$\mathbb E[N]=mH_n+1.$$

各轮独立同分布，$N$ 是以完整轮次结果为信息的停时，且期望有限。由 Wald 等式，所求总时间期望为

$$\boxed{ \mathbb E[T] =(mH_n+1)\frac{n+m+1}{m+1} }.$$

全部分母均小于模数 $998244353$，可以用模逆元完成计算。

做法

子任务 1

当 $n=1$ 时，$H_1=1$，公式直接化为 $m+2$，时间和额外空间均为 $O(1)$。

子任务 2

当 $n\le15$ 时，可以直接枚举所有非空数字牌子集。若子集大小为 $k$，就把

$$(-1)^{k+1}\frac{m+k}{k}$$

加入 $\mathbb E[N]$，最后乘以一轮的期望长度。时间复杂度为 $O(2^n\log 998244353)$，额外空间复杂度为 $O(1)$。

子任务 3

先使用上面的化简式，只需计算 $H_n$。对每个 $1\le i\le n$ 独立使用快速幂计算 $i^{-1}$，时间复杂度为 $O(n\log 998244353)$，额外空间复杂度为 $O(1)$。

子任务 4

在素数模数 $p=998244353$ 下，逆元满足

$$\operatorname{inv}[1]=1, \qquad \operatorname{inv}[i] =p-\left\lfloor\frac pi\right\rfloor \operatorname{inv}[p\bmod i]\bmod p.$$

线性递推所有 $1$ 到 $n$ 的逆元并求和，即可得到 $H_n$。最后代入闭式。

时间复杂度为 $O(n+\log p)$，空间复杂度为 $O(n)$。

复杂度

四个层级的时间复杂度依次为 $O(1)$、$O(2^n\log p)$、$O(n\log p)$ 和 $O(n+\log p)$；对应的额外空间复杂度依次为 $O(1)$、$O(1)$、$O(1)$ 和 $O(n)$。

正确性证明

一轮长度公式由对每张数字牌的指示变量求和得到。轮数公式由尾和公式与“指定 $k$ 张牌在一轮全部缺失”的精确概率做容斥得到。两个容斥和分别化为 $1$ 与 $H_n$，所以 $\mathbb E[N]=mH_n+1$。最后 Wald 等式把独立同分布轮次的总长度期望化为 $\mathbb E[N]\mathbb E[X]$。因此算法输出的闭式正是游戏总时间的期望。