AT_agc076_d.[AGC076D] Stochastic Dominance

令 $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$ 到 $k$，以及 $k$ 个蓝球，同样编号为 $1$ 到 $k$。现在，你将以如下方式在每个球上写一个实数（所有的随机选择都是相互独立的）：

• 对于每个 $1 \leq i \leq k$，红球 $i$ 上写的数字为 $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\not\equiv 0 \pmod{998244353}$。因此，唯一存在一个整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出 $R$。

输入按以下格式从标准输入给出：

$N$ $M$ $A_1$ $A_2$ $ \cdots $ $A_M$

输出 $N$ 行，其中第 $i$ 行输出 $k=i$ 时的答案。

样例解释 1

• $k=1$：满足条件的概率为 $1/2$。
• $k=2$：满足条件的概率为 $5/16$。

数据范围

• $1 \leq N \leq 250000$
• $1 \leq M \leq 250000$
• $0 \leq A_i < L=10^8$
• 所有输入数值均为整数。

由 ChatGPT 5 翻译