ゆるふわ競技プログラミングオンサイト at FORCIA #9
コンテスト日時
2026/11/07 (Sa) 14:15 - 16:45

I - Hypercube Interior Paths

ผักชี
2
s
1024
MB
1000
点

問題文

正の整数 $N, D$ が与えられます。各整数 $d = 1, 2, \ldots, D$ について、以下の問題を解いてください。

$d$ 次元空間において、各座標が $0$ 以上 $N$ 以下の整数であるような格子点 $(x_1, x_2, \ldots, x_d)$ 全体からなる集合を考えます。

あなたは最初、格子点 $(0, 0, \ldots, 0)$ にいます。ここから1回の移動で「いずれか1つの座標の値を $1$ 増やす」という操作を $Nd$ 回繰り返すことで、格子点 $(N, N, \ldots, N)$ へと向かう最短経路を考えます。

移動の途中で、内部の格子点を1回以上通るような最短経路の総数を $998244353$ で割った余りを求めてください。

ただし、内部の格子点とは、すべての整数 $i$($1 \leq i \leq d$)について $0 < x_i < N$ を満たす格子点 $(x_1, x_2, \ldots, x_d)$ のことを指します。

制約

  • $2 \leq N$
  • $1 \leq D \leq 2\times10^5$
  • $ND \leq 5\times10^6$
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

$N$ $D$

出力

$d = 1, 2, \ldots, D$ に対する答えをそれぞれ $A_1, A_2, \ldots, A_D$ とするとき、以下の形式で空白区切りで1行に出力してください。

$A_1$ $A_2$ $\ldots$ $A_D$

入力例 1
2 3
出力例 1
1 4 36
  • $d = 1$ のとき、内部の格子点は $(1)$ のみであり、条件を満たす最短経路は $(0) \to (1) \to (2)$ の $1$ 通りです。
  • $d = 2$ のとき、内部の格子点は $(1, 1)$ のみです。$(0, 0)$ から $(1, 1)$ への最短経路が $2$ 通り、$(1, 1)$ から $(2, 2)$ への最短経路が $2$ 通りあるため、条件を満たす最短経路は $2 \times 2 = 4$ 通りです。
  • $d = 3$ のとき、内部の格子点は $(1, 1, 1)$ のみです。$(0, 0, 0)$ から $(1, 1, 1)$ への最短経路が $6$ 通り、$(1, 1, 1)$ から $(2, 2, 2)$ への最短経路が $6$ 通りあるため、条件を満たす最短経路は $6 \times 6 = 36$ 通りです。
入力例 2
5 4
出力例 2
1 250 740250 280688117

$998244353$ で割った余りを出力してください。

提出
C++23 (g++ 12.2.0)