分数: 500 点
问题陈述
有 N 卡叫卡 1,卡 2, \ldots,卡 N。卡上 i (1\leq i\leq N),一个整数 A_i 。
对于 K=1, 2, \ldots, N,解决以下问题。
我们有一个袋子,里面装有 K 卡片:卡片 1,卡 2, \ldots,卡 K.
让我们执行两次以下操作,并让 x 和 y 是按记录顺序记录的数字。从袋子里均匀随机抽取一张卡片,并记录该卡片上写的数字。然后, 将卡放回包里.
打印期望值 \max(x,y),模数 998244353 (见注释)。
在这里, \max(x,y) 表示以下值中的较大者 x 和 y (或 x 如果它们相等)。
注释
可以证明,所求的期望值总是有限且有理的。此外,在该问题的约束下,当该值表示为 \frac{P}{Q} 具有两个互质整数 P 和 Q,可以证明存在唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。打印此内容 R.
约束
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 2\times 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印 N 行。的 i第行 (1\leq i\leq N) 应包含问题的答案 K=i.
示例输入 1
3 5 7 5
示例输出 1
5 499122183 443664163
例如,答案 发现 K=2 如下。
包内含卡 1 和卡 2,与 上面分别写着 A_1=5 和 A_2=7 。
- 如果你抓牌 1 在第一次抽奖和抽牌 1 再次在第二次抽奖中,我们有 x=y=5,所以 \max(x,y)=5.
- 如果你抓牌 1 在第一次抽奖和抽牌 2 在第二次抽奖中,我们有 x=5 和 y=7,所以 \max(x,y)=7.
- 如果你抓牌 2 在第一次抽奖和抽牌 1 在第二次抽奖中,我们有 x=7 和 y=5,所以 \max(x,y)=7.
- 如果你抓牌 2 在第一次抽奖和抽牌 2 再次在第二次抽奖中,我们有 x=y=7,所以 \max(x,y)=7.
这些事件以相同的概率发生,因此寻求的期望值为 \frac{5+7+7+7}{4}=\frac{13}{2}。 我们有 499122183\times 2\equiv 13 \pmod{998244353},所以 499122183 。
示例输入 2
7 22 75 26 45 72 81 47
示例输出 2
22 249561150 110916092 873463862 279508479 360477194 529680742