102156: [AtCoder]ABC215 G - Colorful Candies 2

Problem Statement

There are $N$ candies arranged in a row from left to right.
Each candy has one of the following $10^9$ colors: Color $1$, Color $2$, $\ldots$, Color $10^9$.
For each $i = 1, 2, \ldots, N$, the $i$-th candy from the left has Color $c_i$.

Takahashi will choose $K$ from the $N$ candies and get those $K$ candies.
There are $\binom{N}{K}$ ways to choose $K$ from the $N$ candies, where $\binom{N}{K}$ is a binomial coefficient. Takahashi will randomly select one of these $\binom{N}{K}$ ways with equal probability.

Because Takahashi wants to eat colorful candies, the more variety of colors his candies have, the happier he will be.
For each scenario $K = 1, 2, \ldots, N$, find the expected value of the number of different colors Takahashi's candies will have.
We can prove that the sought value is a rational number. Print this rational number modulo $998244353$, as described in Notes.

Notes

When you print a rational number, first write it as a fraction $\frac{y}{x}$, where $x, y$ are integers and $x$ is not divisible by $998244353$ (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer $z$ between $0$ and $P - 1$, inclusive, that satisfies $xz \equiv y \pmod{998244353}$.

Constraints

• $1 \leq N \leq 5 \times 10^4$
• $1 \leq c_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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.

Sample Input 1

3
1 2 2

Sample Output 1

1
665496237
2

When $K = 1$, he will get the $1$-st candy, $2$-nd candy, or $3$-rd candy. In any case, his candy will have one color, so the expected value of the number of different colors is $1$.

When $K = 2$, he will get the $1$-st and $2$-nd candies, $2$-nd and $3$-rd candies, or $1$-st and $3$-rd candies.

• If he gets the $1$-st and $2$-nd candies, they have two different colors.
• If he gets the $2$-nd and $3$-rd candies, they have one color.
• If he gets the $1$-st and $3$-rd candies, they have two different colors.

Thus, the expected value of the number of different colors is $\frac{1}{3} \cdot 2 + \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 2 = \frac{5}{3}$.
Be sure to print it modulo $998244353$ as described in Notes.

When $K = 3$, he will always get the $1$-st, $2$-nd, and $3$-rd candies, which have two different colors, so the expected value of the number of different colors is $2$.

Sample Input 2

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

Sample Output 2

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7

问题描述

从左到右有$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$，找出高桥糖果将具有的不同颜色数量的期望值。

我们可以证明所求值是一个有理数。根据Notes中的描述，将这个有理数对$998244353$取模打印。

注意

当你打印一个有理数时，首先要将其写为$\frac{y}{x}$的形式，其中$x, y$是整数且$x$不被$998244353$整除（在问题的约束下，这种表示总是可能的）。

然后，你需要打印一个在$0$到$P - 1$之间的整数$z$，满足$xz \equiv y \pmod{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$行应包含对于场景$K = i$，高桥糖果将具有的不同颜色数量的期望值，按照Notes中的描述对$998244353$取模打印。

样例输入1

3
1 2 2

样例输出1

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}$。

请确保按照Notes中的描述对$998244353$取模打印。

当$K = 3$时，他将总是获得第$1$，$2$，和$3$颗糖果，它们有两种不同的颜色，所以不同颜色数量的期望值为$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