分数: 1400 点
问题陈述
让 L=10^8.
给你一个整数 N 和一个非负整数序列 A=(A_1,A_2,\cdots,A_M) 长度 M (0 \leq A_i < L)。 对于每个 k=1,2,\cdots,N,解决以下问题:
有 k 红球编号为 1 to k 和 k 蓝色球编号为 1 to k。 现在,您将按照以下方式在每个球上写下一个实数。 在这里,所有随机选择都是独立的。
-
对于每个 1 \leq i \leq k,红球上写的数字 i is L \times (i-1)+A_{j_i}。 在这里, j_i 是从以下范围内均匀随机选择的整数 1 和 M (含)。
-
对于每个 1 \leq i \leq k,蓝色球上写的数字 i 是 实数 从范围中均匀随机选择 [0,k \times L).
求概率,模 998244353,在所有球上写上数字后满足以下条件。
- 对于任何实数 x (0 \leq x \leq k \times L), "最多写有数字的红球数量 x" \geq “最多写有数字的蓝色球的数量 x".
概率模的定义 998244353
可以证明,期望的概率总是有理数。另外,在该问题的约束下,可以证明,如果所需的有理数表示为不可约分数 \frac{P}{Q},那么 Q \neq 0 \pmod{998244353}。因此,唯一存在一个整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353。输出这个 R.
约束
- 1 \leq N \leq 250000
- 1 \leq M \leq 250000
- 0 \leq A_i < L=10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \cdots A_M
输出
输出 N 行。 的 i- 第行应包含以下问题的答案 k=i.
示例输入 1
2 1 50000000
示例输出 1
499122177 686292993
- k=1:满足条件的概率为 1/2.
- k=2:满足条件的概率为 5/16.
示例输入 2
3 5 78682095 25048034 71067122 94666780 1927105
示例输出 2
741897823 406774904 435399949
示例输入 3
10 7 40490214 25131781 2271243 52064315 34467030 27419560 56103210
示例输出 3
457696464 497746652 679391958 742383895 245278311 709723420 729551291 1911348 414224424 650563524