S - ゲーム 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 6 点

問題文

次の問題を 部分問題 と呼びます。

頂点に 1 から N の番号がついた N 頂点の木および整数 K が与えられます。ここで K=1 または K=N が成り立ちます。
Alice と Bob がゲームをします。ゲームは以下の手順で進行します。

  • まず、Alice が頂点 1, 頂点 2, \dots, 頂点 K のいずれかに駒を 1 個置く。
  • その後、Bob から初めて交互に次の操作を繰り返す：駒が置かれている頂点に隣接する頂点のうちまだ駒が置かれたことがない頂点を 1 個選び、その頂点に駒を動かす。
  • 自分の手番で操作ができなくなった人が負けで、そうでない人が勝ちとなる。

双方が最適にゲームをした時、勝つのはどちらですか？

整数 U および \mathrm{type} \in \lbrace 1, 2 \rbrace が与えられます。
N = 2, 3, \dots, U について次の問題を解いてください。

  • 整数 N, K が与えられる。ここで K の値は \mathrm{type}=1 のとき 1 を、\mathrm{type}=2 のとき N を取る。
    この N, K が部分問題の N, K と一致するとする。この時、部分問題の入力としてあり得る、頂点に 1 から N の番号がついた N 頂点の木は N^{N-2} 個あるが、このうち部分問題の答えが Alice であるような木の個数を 998244353 で割った余りを求めよ。

制約

  • 2 \leq U \leq 2.5 \times 10^5
  • \mathrm{type} \in \lbrace 1, 2 \rbrace
  • 入力される値は全て整数

配点

この問題は次のように採点される。

  • \mathrm{type}=1 を満たすデータセットに正解した場合、3 点が与えられる。
  • \mathrm{type}=2 を満たすデータセットに正解した場合、3 点が与えられる。

入力

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

U \mathrm{type}

出力

U-1 行出力せよ。i 行目には N=i+1 の時の答えを出力せよ。

入力例 1

4 1

出力例 1

0
2
3

\mathrm{type}=1 の時、常に K=1 が成り立ちます。
N=3 の場合、条件を満たす木は 1-2-3 と辺が結ばれた木と 1-3-2 と辺が結ばれた木の 2 個です。

入力例 2

10 2

出力例 2

0
3
4
125
576
16807
154624
4782969
69760000

\mathrm{type}=2 の時、常に K=N が成り立ちます。

Score: 6 points

Problem Statement

We define the following as a subproblem:

You are given a tree with N vertices labeled 1 through N, and an integer K where K=1 or K=N.
Alice and Bob play a game with the following rules:

  • First, Alice places a piece on one of the vertices 1, 2, \dots, K.
  • Then, starting with Bob, they alternately perform the following operation:
    • Choose a vertex adjacent to the current piece that has not yet been visited, and move the piece there.
  • The player who cannot make a move on their turn loses, and the other player wins.

Assuming both play optimally, determine who wins the game.

You are given an integer U and a value \mathrm{type} \in {1, 2}.
For each N = 2, 3, \dots, U, solve the following problem:

  • You are given integers N and K, where
    K = 1 if \mathrm{type} = 1, and K = N if \mathrm{type} = 2.
    Suppose these values match the N and K of the subproblem above. There are N^{N-2} possible trees with N vertices labeled 1 through N.
    Among them, count how many trees yield the answer "Alice" for the subproblem, and output the result modulo 998244353.

Constraints

  • 2 \leq U \leq 2.5 \times 10^5
  • \mathrm{type} \in {1, 2}
  • All input values are integers

Scoring

This problem has the following scoring rules:

  • If you solve all datasets with \mathrm{type} = 1, you will earn 3 points.
  • If you solve all datasets with \mathrm{type} = 2, you will earn 3 points.

Input

The input is given from standard input in the following format:

U \mathrm{type}

Output

Print U - 1 lines. On the i-th line, output the answer for N = i + 1.

Sample Input 1

4 1

Sample Output 1

0
2
3

When \mathrm{type} = 1, K = 1 always holds.
For N = 3, there are 2 valid trees: one with edges 1-2-3, and another with edges 1-3-2.

Sample Input 2

10 2

Sample Output 2

0
3
4
125
576
16807
154624
4782969
69760000

When \mathrm{type} = 2, K = N always holds.