分数: 650 点
问题陈述
新年快乐!说到新年的室内游戏,那就是双六!
有一个双六棋盘,包括 N+1 方块:方块 0,方形 1, \dots,方形 N.
有一个 M产生正整数的单面骰子(骰子) A_1, A_2, \dots, A_M 具有相同的概率。在这里, A_1, A_2, \dots, A_M 是不同的。
人 1, 人 2, \dots, 人 L 将使用该板玩游戏。游戏进行如下:
- 最初,放置 L 件,件 1,一块 2, \dots,一块 L,在广场上 0.
- 回合以人开始的数字顺序进行 1。严格来说,人后 i轮到了,轮到人了 (i \bmod L) + 1。每个人轮流执行以下操作:
- 让 i 是轮到的人的号码。掷骰子。让 x 是正方形,其中一块 i 位于并且 y 是骰子上出现的整数,并移动棋子 i 到正方形 \min(N, x+y).
- 第一个将编号的棋子放在正方形上的人 N 赢了,其他人输了。
对于 i =1,2,\dots,L,求概率,模 998244353,那个人 i 获胜。
什么是概率 \text{mod }998244353?
可以证明,找到的概率总是有理数。 另外,在该问题的约束下,当值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,可以证明恰好存在一个整数 R 满足 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.约束
- 1 \leq N \leq 2.5 \times 10^5
- 1 \leq M \leq N
- 2 \leq L \leq 2.5 \times 10^5
- 1 \leq A_1 \lt A_2 \lt \dots \lt A_M \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M L A_1 A_2 \dots A_M
输出
输出 L 行。的 i- 第行应包含该人的概率 i 赢得比赛,计算模数 998244353.
示例输入 1
2 2 3 1 2
示例输出 1
374341633 748683265 873463809
人 1 获胜的概率 \frac{5}{8}, 人 2 获胜的概率 \frac{1}{4}和人 3 获胜的概率 \frac{1}{8}.
示例输入 2
100 2 4 20 26
示例输出 2
164734081 939753473 943409153 946836353
示例输入 3
123456 12 10 21994 29598 47718 59035 69293 73766 74148 76721 98917 104184 120533 122441
示例输出 3
580013367 81975961 178650340 610261473 14826260 541995390 307779600 913805572 76177928 687491522