Double Chance

题目描述

有 $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$）。

输入格式

输入从标准输入给出，格式如下： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出 $N$ 行。第 $i$ 行 $(1\leq i\leq N)$ 应包含对于 $K=i$ 的问题的答案。

3
5 7 5

5
499122183
443664163

7
22 75 26 45 72 81 47

22
249561150
110916092
873463862
279508479
360477194
529680742

提示

$1 \leq N \leq 2\times 10^5$ $1 \leq A_i \leq 2\times 10^5$ 输入中的所有数值均为整数。可以证明，所求的期望值总是有限且为有理数。此外，在本题的约束下，当该值表示为互质整数 $P$ 和 $Q$ 的分数 $\frac{P}{Q}$ 时，可证明存在唯一整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。输出该 $R$。例如，$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$.

标签: AtCoder|abc276F

来源

AtCoder|abc276F