Ex - Colorfulness
当前没有测试数据。
Ex - 色彩浓度
分值：$600$ 分
问题描述
有 $N$ 个编号为 $1$ 到 $N$ 的球。第 $i$ 个球被涂上颜色 $a_i$。
对于排列 $P = (P_1, P_2, \dots, P_N)$，我们定义 $C(P)$ 如下：
- 将球 $P_1, P_2, \dots, P_N$ 按照这个顺序排成一行，$C(P)$ 表示相邻球颜色不同的对数。
设 $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$
- 输入中的所有值都是整数。
输入
输入包含以下格式的标准输入：
输出
按照以下格式输出答案：
``` $F(1)$ $F(2)$ $\dots$ $F(M)$ ```3 4
1 1 2
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 1
1 1
0
10 5
3 1 4 1 5 9 2 6 5 3
30481920 257886720 199419134 838462446 196874334