L - Random Mex Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 です。