AT_abc345_g [ABC345G] Sugoroku 5

题目描述

有一个由 $N+1$ 个格子组成的双六棋盘，编号为 $0$、$1$、$\dots$、$N$。
另外，有一个可以等概率掷出 $1$ 到 $K$ 之间整数的骰子。
一开始，你在格子 $0$。你会重复以下操作直到到达格子 $N$：

• 掷骰子。设你当前在格子 $x$，骰子掷出的数为 $y$，则你移动到格子 $\min(N,\ x+y)$。

设恰好经过 $i$ 次操作到达格子 $N$ 的概率为 $P_i$。请计算 $P_1,\ P_2,\ \dots,\ P_N$，并对 $998244353$ 取模输出。

概率 $\bmod\ 998244353$ 的含义如下：可以证明，所求概率一定是有理数。在本题的约束下，若用互质的两个整数 $P$、$Q$ 表示为 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $K$

输出格式

输出 $N$ 行。第 $i$ 行输出 $P_i$ 对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

3 2

输出 #1

0
249561089
748683265

输入输出样例 #2

输入 #2

5 5

输出 #2

598946612
479157290
463185380
682000542
771443236

输入输出样例 #3

输入 #3

10 6

输出 #3

0
166374059
207967574
610038216
177927813
630578223
902091444
412046453
481340945
404612686

说明/提示

限制条件

• $1 \leq K \leq N \leq 2 \times 10^5$
• $N,\ K$ 均为整数

样例解释 1

例如，恰好经过 $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}$，所以输出 $P_2$ 时应为 $249561089$。

由 ChatGPT 4.1 翻译