Colorful Candies 2

题目描述

有 $N$ 个糖果从左到右排成一行。
每个糖果的颜色是以下 $10^9$ 种颜色之一：颜色 $1$、颜色 $2$、$\ldots$、颜色 $10^9$.
对于每个 $i = 1, 2, \ldots, N$，从左数第 $i$ 个糖果的颜色为 $c_i$。 Takahashi 将从 $N$ 个糖果中选择 $K$ 个并获得这 $K$ 个糖果。
从 $N$ 个糖果中选择 $K$ 个有 $\binom{N}{K}$ 种方法，其中 $\binom{N}{K}$ 是二项式系数。Takahashi 将以相等概率随机选择这 $\binom{N}{K}$ 种方法中的一种。 因为 Takahashi 想吃颜色多样的糖果，他得到的糖果颜色种类越多越高兴。
对于每种情况 $K = 1, 2, \ldots, N$，求 Takahashi 所得到的糖果颜色种类数的期望值。
我们可以证明所求的值是有理数。按照备注中的描述，将该有理数对 $998244353$ 取模后输出。

输入格式

输入从标准输入按如下格式给出： $N$ $c_1$ $c_2$ $\ldots$ $c_N$

输出格式

输出 $N$ 行。第 $i$ 行应包含在情形 $K = i$ 下 Takahashi 所得到的糖果颜色种类数的期望值，对 $998244353$ 取模后的结果，按备注中的描述输出。

3
1 2 2

1
665496237
2

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

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7

提示

$1 \leq N \leq 5 \times 10^4$ $1 \leq c_i \leq 10^9$ 输入中的所有数值都是整数。当你输出一个有理数时，先把它写成分数 $\frac{y}{x}$ 的形式，其中 $x, y$ 是整数且 $x$ 不被 $998244353$ 整除 （在本题约束下，总能得到这样的表示）。然后，输出唯一的整数 $z$，满足 $0 \le z \le P - 1$ 且 $xz \equiv y \pmod{998244353}$。当 $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$.

标签: AtCoder|abc215G

来源

AtCoder|abc215G