/ 
Time Limit: 12 sec / Memory Limit: 1024 MB
配点 : 675 点
問題文
マス 0, マス 1, \dots, マス N の N+1 個のマスからなるスゴロクがあります。
また、1 以上 K 以下の整数が等確率で出るサイコロがあります。
はじめ、あなたはマス 0 にいます。あなたはマス N に着くまで次の操作を繰り返します。
- サイコロを振る。今いるマスを x 、サイコロで出た整数を y としてマス \min(N, x + y) に移動する。
ちょうど i 回の操作によってマス N に着く確率を P_i とします。P_1, P_2, \dots, P_N を \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 K \leq N \leq 2 \times 10^5
- N, K は整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
N 行出力せよ。i 行目には P_i を \text{mod }998244353 で出力せよ。
入力例 1
3 2
出力例 1
0 249561089 748683265
例えば、ちょうど 2 回の操作でマス N に辿り着くのは以下の整数がサイコロで出たときです。
- 1 回目の操作で 1 が出て、2 回目の操作で 2 が出る
- 1 回目の操作で 2 が出て、2 回目の操作で 1 が出る
- 1 回目の操作で 2 が出て、2 回目の操作で 2 が出る
よって P_2 = \left( \frac{1}{2} \times \frac{1}{2} \right) \times 3 = \frac{3}{4} です。249561089 \times 4 \equiv 3 \pmod{998244353} なので 249561089 を P_2 として出力します。
入力例 2
5 5
出力例 2
598946612 479157290 463185380 682000542 771443236
入力例 3
10 6
出力例 3
0 166374059 207967574 610038216 177927813 630578223 902091444 412046453 481340945 404612686
Score: 675 points
Problem Statement
There is a board game with N+1 squares: square 0, square 1, \dots, square N.
You have a die (dice) that rolls an integer between 1 and K, inclusive, with equal probability for each outcome.
You start on square 0. You repeat the following operation until you reach square N:
- Roll the dice. Let x be the current square and y be the rolled number, then move to square \min(N, x + y).
Let P_i be the probability of reaching square N after exactly i operations. Calculate P_1, P_2, \dots, P_N modulo 998244353.
What is probability modulo 998244353?
It can be proved that the sought probabilities will always be rational numbers. Under the constraints of this problem, it can also be proved that when expressing the values as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R satisfying R \times Q \equiv P\pmod{998244353} and 0 \leq R < 998244353. Find this R.Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- N and K are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print N lines. The i-th line should contain P_i modulo 998244353.
Sample Input 1
3 2
Sample Output 1
0 249561089 748683265
For example, you reach square N after exactly two operations when the die rolls the following numbers:
- A 1 on the first operation, and a 2 on the second operation.
- A 2 on the first operation, and a 1 on the second operation.
- A 2 on the first operation, and a 2 on the second operation.
Therefore, P_2 = \left( \frac{1}{2} \times \frac{1}{2} \right) \times 3 = \frac{3}{4}. We have 249561089 \times 4 \equiv 3 \pmod{998244353}, so print 249561089 for P_2.
Sample Input 2
5 5
Sample Output 2
598946612 479157290 463185380 682000542 771443236
Sample Input 3
10 6
Sample Output 3
0 166374059 207967574 610038216 177927813 630578223 902091444 412046453 481340945 404612686