Ex - Colorfulness Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

1 から N までの番号がついた N 個のボールがあります。ボール i には色 a_i がついています。

(1, 2, \dots, N) を並べ替えた列 P = (P_1, P_2, \dots, P_N) に対して C(P) を次のように定めます。

  • ボールを P_1, P_2, \dots, P_N という順番に一列に並べたときの、異なる色のボールが隣り合っている場所の数。

(1, 2, \dots, N) を並べ替えた列全体の集合を S_N と置きます。また、F(k) を次のように置きます。

\displaystyle F(k) = \left(\sum_{P \in S_N}C(P)^k \right) \bmod 998244353

F(1), F(2), \dots, F(M) を列挙してください。

制約

  • 2 \leq N \leq 2.5 \times 10^5
  • 1 \leq M \leq 2.5 \times 10^5
  • 1 \leq a_i \leq N
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 a_2 \dots a_N

出力

答えを以下の形式で出力せよ。

F(1) F(2) \dots F(M)

入力例 1

3 4
1 1 2

出力例 1

8 12 20 36

(P, C(P)) の組としてあり得るものを列挙すると次のようになります。

  • P=(1,2,3) のとき C(P) = 1
  • P=(1,3,2) のとき C(P) = 2
  • P=(2,1,3) のとき C(P) = 1
  • P=(2,3,1) のとき C(P) = 2
  • P=(3,1,2) のとき C(P) = 1
  • P=(3,2,1) のとき C(P) = 1

これらの値を F(k) に代入すれば答えを計算することができます。例えば F(1) = 1^1 + 2^1 + 1^1 + 2^1 + 1^1 + 1^1 = 8 です。

入力例 2

2 1
1 1

出力例 2

0

入力例 3

10 5
3 1 4 1 5 9 2 6 5 3

出力例 3

30481920 257886720 199419134 838462446 196874334

Score : 600 points

Problem Statement

There are N balls numbered 1 through N. Ball i is painted in Color a_i.

For a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N), let us define C(P) as follows:

  • The number of pairs of adjacent balls with different colors when Balls P_1, P_2, \dots, P_N are lined up in a row in this order.

Let S_N be the set of all permutations of (1, 2, \dots, N). Also, let us define F(k) by:

\displaystyle F(k) = \left(\sum_{P \in S_N}C(P)^k \right) \bmod 998244353.

Enumerate F(1), F(2), \dots, F(M).

Constraints

  • 2 \leq N \leq 2.5 \times 10^5
  • 1 \leq M \leq 2.5 \times 10^5
  • 1 \leq a_i \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 \dots a_N

Output

Print the answers in the following format:

F(1) F(2) \dots F(M)

Sample Input 1

3 4
1 1 2

Sample Output 1

8 12 20 36

Here is the list of all possible pairs of (P, C(P)).

  • If P=(1,2,3), then C(P) = 1.
  • If P=(1,3,2), then C(P) = 2.
  • If P=(2,1,3), then C(P) = 1.
  • If P=(2,3,1), then C(P) = 2.
  • If P=(3,1,2), then C(P) = 1.
  • If P=(3,2,1), then C(P) = 1.

We may obtain the answers by assigning these values into F(k). For instance, F(1) = 1^1 + 2^1 + 1^1 + 2^1 + 1^1 + 1^1 = 8.

Sample Input 2

2 1
1 1

Sample Output 2

0

Sample Input 3

10 5
3 1 4 1 5 9 2 6 5 3

Sample Output 3

30481920 257886720 199419134 838462446 196874334