← 返回题目列表

AtCoder · tupc2023_l

L. 随机墨西哥

中文机器翻译题面 查看原题

配点 : 100 点

問題文

0 以上 M 随机选择小于的整数的操作 执行 N 次。i 所选号码 A_i 什么时候 \mathrm{mex}\big(A_1,A_2,\dots,A_N\big) 的预期值为 使用 \text{mod}\,998244353 找到它。

但是, 表示\mathrm{mex}\big(A_1,A_2,\dots,A_N\big) 考虑一块分为 A_1,A_2,\dots,A_N 中不包含的最小非负整数。 您将获得

T 测试用例,因此请找到每个测试用例的答案。

期待値 \text{mod}\,998244353 的定义
可以证明,在这个问题中找到的期望值始终是一个有理数。此外,在该问题的约束下,要寻求的期望值可以表示为不可约分数。 当表示为 \frac{y}{x} 时 保证不能被 {x} 是 998244353 整除。 此时 使其满足 xz≡y\;(\text{mod}\,998244353) 喜欢满足 0 以上 998244352 的整数 z 是唯一确定的。这个 请回答 z 。

制約

  • 1 \leq T \leq 3 \times 10^5
  • 1 \leq N,M \leq 8000
  • 输入都是整数

部分点

  • 附加限制 如果正确答案是满足 T \leq 5,N \leq 100, M \leq 100 的数据集 10 点。

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出。 输出

N M

出力

T 行。 打印第i 在线 i 个测试用例的答案。


入力例 1

4
3 2
1 1
20 23
8000 8000

出力例 1

374341634
1
111675632
994279778
  • 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 。