← 返回题目列表

AtCoder · abc345_g

G. 双六 5

中文机器翻译题面 查看原题

分数: 675 点

问题陈述

有一款棋盘游戏 N+1 正方形:正方形 0,方形 1, \dots,方形 N.
你有一个骰子,可以在之间滚动一个整数 1 和 K,包含在内,每个结果的概率相等。
你从广场开始 0。重复以下操作,直到到达正方形 N:

  • 掷骰子。让 x 是当前方块并且 y 是滚动的数字,然后移动到方格 \min(N, x + y).

让 P_i 是达到平方的概率 N 正好之后 i 操作。计算 P_1, P_2, \dots, P_N 模数 998244353.

什么是概率模 998244353? 可以证明,求的概率总是有理数。 在该问题的约束下,还可以证明,当将值表示为 \frac{P}{Q} 使用两个互质整数 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 经过两次操作后,当骰子掷出以下数字时:

  • A 1 第一次操作时, 2 关于第二次操作。
  • A 2 第一次操作时, 1 关于第二次操作。
  • A 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