AT_abc276_f [ABC276F] Double Chance

题目描述

有 $N$ 张卡片，分别为卡片 $1$、卡片 $2$、$\ldots$、卡片 $N$，每张卡片 $i$（$1\leq i\leq N$）上写有一个整数 $A_i$。

对于 $K=1,2,\ldots,N$，请解决以下问题。

有一个袋子，里面装有卡片 $1$、卡片 $2$、$\ldots$、卡片 $K$ 共 $K$ 张卡片。
重复以下操作 $2$ 次，依次记录下来的数为 $x, y$：

从袋子中随机取出一张卡片，记录卡片上写的数。之后，将卡片放回袋子。

输出 $\max(x, y)$ 的期望值，对 $998244353$ 取模（见注释）。 其中，$\max(x, y)$ 表示 $x$ 和 $y$ 中较大的那个值。

输入格式

输入以以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出 $N$ 行。第 $i$ 行（$1\leq i\leq N$）输出当 $K=i$ 时问题的答案。

输入输出样例 #1

输入 #1

3
5 7 5

输出 #1

5
499122183
443664163

输入输出样例 #2

输入 #2

7
22 75 26 45 72 81 47

输出 #2

22
249561150
110916092
873463862
279508479
360477194
529680742

说明/提示

注释

可以证明，所求的期望值一定是有限且有理数。并且，在本题的约束下，将其表示为互质的两个整数 $P, Q$ 的分数 $\frac{P}{Q}$ 时，存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353}$ 且 $0\leq R<998244353$。请输出这个 $R$。

约束条件

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq 2\times 10^5$
• 输入均为整数

样例解释 1

例如，当 $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$。

由 ChatGPT 4.1 翻译