G - Colorful Candies 2 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色 1、色 2、\ldots 、色 10^9 の、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 のそれぞれの場合について、高橋君がもらうキャンディに含まれる色の種類数の期待値を求めてください。
ここで、求める答えは有理数となることが証明できます。答えとなる有理数を注記で述べるように \bmod 998244353 で出力してください。

注記

有理数を出力する際は、まずその有理数を分数 \frac{y}{x} として表してください。ここで、x, y は整数であり、x は 998244353 で割り切れてはなりません（この問題の制約下で、そのような表現は必ず可能です）。そして、xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の唯一の整数 z を出力してください。

制約

  • 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 の場合における高橋君がもらうキャンディに含まれる色の種類数の期待値を、注記に述べるように \bmod 998244353で出力せよ。

入力例 1

3
1 2 2

出力例 1

1
665496237
2

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} です。
注記に述べたように、\bmod 998244353 で出力することに注意してください。

K = 3 のとき、高橋君がもらうキャンディの組み合わせは、「 1, 2, 3 番目のすべて」の 1 通りのみであり、含まれる色は 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

Score : 600 points

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