AT_abc215_g [ABC215G] Colorful Candies 2

题目描述

有 $N$ 个糖果从左到右排成一列。
每个糖果的颜色是 $10^9$ 种颜色中的某一种，分别为颜色 $1$、颜色 $2$、$\ldots$、颜色 $10^9$。
对于 $i=1,2,\ldots,N$，从左到右第 $i$ 个糖果的颜色为 $c_i$。

高桥君会从排成一列的 $N$ 个糖果中选出 $K$ 个，并获得这 $K$ 个糖果。
从 $N$ 个糖果中选出 $K$ 个的组合数可以用二项式系数 $\binom{N}{K}$ 表示。高桥君会等概率地随机选择 $\binom{N}{K}$ 种选法中的一种。

高桥君希望吃到更多不同颜色的糖果，因此他获得的糖果中包含的颜色种类数越多，他就越开心。
请对于 $K=1,2,\ldots,N$ 的每一种情况，求出高桥君获得的糖果中包含的颜色种类数的期望值。
这里，要求的答案可以表示为有理数。请按照注记中的说明，输出对 $998244353$ 取模后的结果。

输入格式

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

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

输出格式

请输出 $N$ 行。第 $i$ 行输出 $K=i$ 时高桥君获得的糖果中包含的颜色种类数的期望值，按照注记中的说明对 $998244353$ 取模后输出。

输入输出样例 #1

输入 #1

3
1 2 2

输出 #1

1
665496237
2

输入输出样例 #2

输入 #2

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

输出 #2

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7

说明/提示

注记

输出有理数时，首先将其表示为分数 $\frac{y}{x}$，其中 $x, y$ 为整数，且 $x$ 不能被 $998244353$ 整除（在本题的约束下，总能找到这样的表示）。然后，输出唯一满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod{998244353}$ 的整数 $z$。

约束条件

• $1 \leq N \leq 5 \times 10^4$
• $1 \leq c_i \leq 10^9$
• 输入均为整数

样例解释 1

当 $K=1$ 时，高桥君获得糖果的组合有“仅第 1 个”、“仅第 2 个”、“仅第 3 个”共 3 种情况。每种情况下，包含的颜色都是 1 种。因此，包含的颜色种类数的期望值为 1。

当 $K=2$ 时，高桥君获得糖果的组合有“第 1 个和第 2 个”、“第 2 个和第 3 个”、“第 1 个和第 3 个”共 3 种情况。

• 获得“第 1 个和第 2 个”时，包含的颜色为 2 种
• 获得“第 2 个和第 3 个”时，包含的颜色为 1 种
• 获得“第 1 个和第 3 个”时，包含的颜色为 2 种

因此，包含的颜色种类数的期望值为 $\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 种。因此，包含的颜色种类数的期望值为 2。

由 ChatGPT 4.1 翻译