G - Sugoroku 6 解説 /

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

配点 : 650 点

問題文

あけましておめでとうございます！正月の家遊びといえばスゴロクですね！

マス 0, マス 1, \dots, マス N の N+1 個のマスからなるスゴロクがあります。
また、正整数 A_1, A_2, \dots, A_M が等確率で出る M 面サイコロがあります。ここで A_1, A_2, \dots, A_M は相異なります。
人 1, 人 2, \dots, 人 L がこのスゴロクを使ってゲームをすることにしました。ゲームの手順は次の通りです：

  • 初めに駒 1, 駒 2, \dots, 駒 L の L 個の駒をマス 0 に置く。
  • 人 1 から始めて番号順に手番が回ってくる。厳密に言うと、人 i の手番の次に人 (i \bmod L) + 1 に手番が回る。各人は自身の手番で次の操作を行う：
    • 手番である人の番号を i とする。サイコロを振る。駒 i があるマスを x、サイコロで出た整数を y としてマス \min(N, x+y) に駒 i を移動する。
  • はじめに自分の番号の駒をマス N に置くことができた人が勝ちで、他の人は負けとなる。

i =1,2,\dots,L について人 i が勝利する確率を \text{mod }998244353 で求めてください。

確率 \text{mod }998244353 とは？ 求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

  • 1 \leq N \leq 2.5 \times 10^5
  • 1 \leq M \leq N
  • 2 \leq L \leq 2.5 \times 10^5
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_M \leq N
  • 入力される値は全て整数

入力

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

N M L
A_1 A_2 \dots A_M

出力

L 行出力せよ。i 行目にはゲームで人 i が勝利する確率を \text{mod }998244353 で計算した値を出力せよ。

入力例 1

2 2 3
1 2

出力例 1

374341633
748683265
873463809

人 1 が勝つ確率は \frac{5}{8}、人 2 が勝つ確率は \frac{1}{4}、人 3 が勝つ確率は \frac{1}{8} です。

入力例 2

100 2 4
20 26

出力例 2

164734081
939753473
943409153
946836353

入力例 3

123456 12 10
21994 29598 47718 59035 69293 73766 74148 76721 98917 104184 120533 122441

出力例 3

580013367
81975961
178650340
610261473
14826260
541995390
307779600
913805572
76177928
687491522

Score : 650 points

Problem Statement

Happy New Year! When it comes to indoor play on New Year's, it's sugoroku!

There is a sugoroku board consisting of N+1 squares: squares 0, square 1, \dots, square N.
There is an M-sided die (dice) that produces positive integers A_1, A_2, \dots, A_M with equal probability. Here, A_1, A_2, \dots, A_M are distinct.
Person 1, person 2, \dots, person L will play a game using this board. The game proceeds as follows:

  • Initially, place L pieces, piece 1, piece 2, \dots, piece L, on square 0.
  • Turns come around in numerical order starting with person 1. Strictly speaking, after person i's turn, the turn goes to person (i \bmod L) + 1. Each person performs the following operation on their turn:
    • Let i be the number of the person whose turn it is. Roll the die. Let x be the square where piece i is located and y be the integer that came up on the die, and move piece i to square \min(N, x+y).
  • The first person to place their numbered piece on square N wins, and the other people lose.

For i =1,2,\dots,L, find the probability, modulo 998244353, that person i wins.

What is probability \text{mod }998244353? It can be proved that the probability to be found is always a rational number. Also, under the constraints of this problem, when the value is expressed as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there exists exactly one integer R that satisfies R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

  • 1 \leq N \leq 2.5 \times 10^5
  • 1 \leq M \leq N
  • 2 \leq L \leq 2.5 \times 10^5
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_M \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M L
A_1 A_2 \dots A_M

Output

Output L lines. The i-th line should contain the probability that person i wins the game, computed modulo 998244353.

Sample Input 1

2 2 3
1 2

Sample Output 1

374341633
748683265
873463809

Person 1 wins with the probability \frac{5}{8}, person 2 wins with the probability \frac{1}{4}, and person 3 wins with the probability \frac{1}{8}.

Sample Input 2

100 2 4
20 26

Sample Output 2

164734081
939753473
943409153
946836353

Sample Input 3

123456 12 10
21994 29598 47718 59035 69293 73766 74148 76721 98917 104184 120533 122441

Sample Output 3

580013367
81975961
178650340
610261473
14826260
541995390
307779600
913805572
76177928
687491522