← 返回题目列表

AtCoder · abc276_f

I. 双重机会

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

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