分数: 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