← 返回题目列表

AtCoder · agc076_d

D. 随机优势

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

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