← 返回题目列表

AtCoder · abc439_g

G. 双六 6

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

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