← 返回题目列表

AtCoder · abc260_h

Ex. 色彩

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 球编号 1 通过 N。 球 i 涂有颜色 a_i.

对于排列 P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N),让我们定义 C(P) 如下:

  • 当 Balls 时,不同颜色的相邻球对的数量 P_1, P_2, \dots, P_N 按此顺序排成一排。

让 S_N 是所有排列的集合 (1, 2, \dots, 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)).

  • If P=(1,2,3),然后 C(P) = 1.
  • If P=(1,3,2),然后 C(P) = 2.
  • If P=(2,1,3),然后 C(P) = 1.
  • If P=(2,3,1),然后 C(P) = 2.
  • If P=(3,1,2),然后 C(P) = 1.
  • If 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