分数: 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