Score: $675$ points

问题陈述

有一个棋盘游戏，共有 $N+1$ 个方格：方格 $0$，方格 $1$，$\dots$，方格 $N$。 你有一枚骰子，它掷出的数字是 $1$ 到 $K$（包括 $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$ 表示这些值时，存在唯一的整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R < 998244353$。找到这个 $R$。

以上为大语言模型 kimi 翻译，仅供参考。

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

update @ 2024/5/16 17:17:27