9480: ABC215 —— G - Colorful Candies 2
[Creator : ]
Description
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.
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.
Input
Input is given from Standard Input in the following format:
```
$N$
$c_1$ $c_2$ $\ldots$ $c_N$
```
```
$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.
Constraints
- $1 \leq N \leq 5 \times 10^4$
- $1 \leq c_i \leq 10^9$
- All values in input are integers.
- $1 \leq c_i \leq 10^9$
- All values in input are integers.
Sample 1 Input
3
1 2 2
Sample 1 Output
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.
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.
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.
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 2 Input
11
3 1 4 1 5 9 2 6 5 3 5
Sample 2 Output
1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7