103456: [Atcoder]ABC345 G - Sugoroku 5

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$.

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

问题描述

有一个棋盘游戏，包含 N+1 个方格：方格 0，方格 1，…，方格 N。

• 你有一个骰子，可以随机掷出 1 到 K 之间的整数，每个结果的概率相等。
• 你从方格 0 开始。重复以下操作，直到你到达方格 N：
• 掷骰子。设当前方格为 x，掷出的数为 y，则移动到方格 $\min(N, x + y)$。

设 $P_i$ 为恰好经过 i 次操作到达方格 N 的概率。计算 $P_1, P_2, \dots, P_N$ 除以 998244353 的余数。

什么是概率除以 998244353？
可以证明，所求的概率始终为有理数。 在本问题的约束下，还可以证明，当用两个互素整数 P 和 Q 表示为 $\frac{P}{Q}$ 时，存在唯一的整数 R 满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R < 998244353$。找到这个 R。

约束条件

• $1 \leq K \leq N \leq 2 \times 10^5$
• N 和 K 是整数。

输入

输入从标准输入中给出，格式如下：

$N$ $K$

输出

打印 N 行。第 i 行应该包含 $P_i$ 除以 998244353 的余数。

样例输入 1

3 2

样例输出 1

0
249561089
748683265

例如，当骰子掷出以下数字时，你将在恰好两次操作后到达方格 N：

• 在第一次操作中掷出 1，在第二次操作中掷出 2。
• 在第一次操作中掷出 2，在第二次操作中掷出 1。
• 在第一次操作中掷出 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