G - 多彩的糖果 2

分数: $600$ 分

问题描述

有 $N$ 个糖果从左到右排成一行。
每个糖果有以下 $10^9$ 种颜色中的一种: 颜色 $1$, 颜色 $2$, $\ldots$, 颜色 $10^9$。
对于每个 $i = 1, 2, \ldots, N$, 第 $i$ 个糖果从左边开始的第 $i$ 个糖果的颜色为 $c_i$。

高桥将从这 $N$ 个糖果中选择 $K$ 个拿走。
从这 $N$ 个糖果中选择 $K$ 个的方式有 $\binom{N}{K}$ 种，其中 $\binom{N}{K}$ 是一个二项式系数。高桥将以相等的概率随机选择这 $\binom{N}{K}$ 种方式中的一种。

由于高桥想吃到多彩的糖果，他的糖果中颜色的种类越多，他就会越开心。
对于每个情况 $K = 1, 2, \ldots, N$，找出高桥的糖果中不同颜色数量的期望值。
我们可以证明所寻找的值是一个有理数。按照注释中的说明，以 $998244353$ 为模打印这个有理数。

注释

在打印一个有理数时，首先将其写成一个分数 $\frac{y}{x}$，其中 $x, y$ 是整数且 $x$ 不可被 $998244353$ 整除 (在问题的限制条件下，这种表示方式始终是可能的)。 然后，你需要打印一个唯一的整数 $z$，满足 $xz \equiv y \pmod{998244353}$，且 $z$ 在 $0$ 到 $P - 1$ 之间（包括 $P$），其中 $P$ 是 $998244353$。

约束

• $1 \leq N \leq 5 \times 10^4$
• $1 \leq c_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入遵循以下格式：

$N$

$c_1$ $c_2$ $\ldots$ $c_N$

输出

输出 $N$ 行。第 $i$ 行应包含高桥的糖果中不同颜色数量的期望值，按照注释中的说明以 $998244353$ 为模打印。

Print $N$ lines. The $i$-th line should contain the expected value of the number of different colors Takahashi's candies will have for the scenario $K = i$, modulo $998244353$ as described in Notes

3
1 2 2

1
665496237
2

当 $K = 1$ 时，他将拿到第 $1$ 个糖果，第 $2$ 个糖果，或者第 $3$ 个糖果。无论哪种情况，他的糖果只有一种颜色，因此不同颜色的期望值为 $1$。

当 $K = 2$ 时，他将拿到第 $1$ 和第 $2$ 个糖果，第 $2$ 和第 $3$ 个糖果，或者第 $1$ 和第 $3$ 个糖果。

• 如果他拿到第 $1$ 和第 $2$ 个糖果，它们有两种不同的颜色。
• 如果他拿到第 $2$ 和第 $3$ 个糖果，它们只有一种颜色。
• 如果他拿到第 $1$ 和第 $3$ 个糖果，它们有两种不同的颜色。

因此，不同颜色的期望值为 $\frac{1}{3} \cdot 2 + \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 2 = \frac{5}{3}$。 按照注释中的说明，请务必以 $998244353$ 为模输出。

当 $K = 3$ 时，他将永远拿到第 $1$、第 $2$ 和第 $3$ 个糖果，这些糖果有两种不同的颜色，因此不同颜色的期望值为 $2$。

11
3 1 4 1 5 9 2 6 5 3 5

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7