AT_tupc2023_l Random Mex

进行 $N$ 次操作，每次从 $0$ 以上 $M$ 未满的整数中等概率地随机选取一个数。第 $i$ 次选取的数字记作 $A_i$，请你求 $ \mathrm{mex}\big(A_1, A_2, \dots, A_N\big) $ 的期望值，并对 $998244353$ 取模。 其中，$ \mathrm{mex}(A_1, A_2, \dots, A_N) $ 表示不在 $A_1, A_2, \dots, A_N$ 中出现的最小的非负整数。 共给出 $T$ 组测试数据，请分别输出每组答案。 期望值 $\bmod\ 998244353$ 的定义：本题中的期望值保证为有理数。设其最简分数为 $ \frac{y}{x} $，其中 $x$ 不会被 $998244353$ 整除。此时，唯一存在一个 $z \in [0,998244352]$ 满足 $xz \equiv y\pmod{998244353}$，请输出该 $z$。

输入按照如下格式从标准输入给出： > $T$ > case$_1$ > ⋮ > case$_T$ 每组测试数据格式如下： > $N$ $M$

输出共 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

### 部分分 - 满足额外约束 $T \leq 5, N \leq 100, M \leq 100$ 的测试点可得 $10$ 分。 ### 样例解释 1 - 对于第 $1$ 组数据，所有可能的 $A$ 为 $(0,0,0)$、$(0,0,1)$、$(0,1,0)$、$(0,1,1)$、$(1,0,0)$、$(1,0,1)$、$(1,1,0)$、$(1,1,1)$ 共 $8$ 种，对应的 $\mathrm{mex}$ 分别是 $1,2,2,2,2,2,2,0$，因此期望值为 $ \dfrac{13}{8} $。 - 对于第 $2$ 组数据，只有 $A=(0)$，故期望值为 $1$。 ### 数据范围 - $1 \leq T \leq 3 \times 10^5$ - $1 \leq N, M \leq 8000$ - 所有输入均为整数。 由 ChatGPT 5 翻译