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 翻译