分数: 600 点
问题陈述
有 N 称为 Person 的人 1, 人 2, \dots, 人 N,按顺序排列成一排 (1,2,\dots,N) 从前面。 人 i 所穿颜色 c_i.
高桥重复以下操作 K 次:选择两人 i 和 j 任意交换Person的位置 i 和人 j.
之后 K 操作已结束,颜色表示 i前面第一个人的穿着与 c_i,对于每个整数 i 这样 1 \leq i \leq N.
人之后有多少种可能的排列 K 操作有哪些? 求计数模数 998244353.
约束
- 2 \leq N \leq 200000
- 1 \leq K \leq 10^9
- 1 \leq c_i \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K c_1 c_2 \dots c_N
输出
打印答案。
示例输入 1
4 1 1 1 2 1
示例输出 1
3
这是高桥可能的操作以及每次操作后人员排列的完整列表。
- 交换 Person 的位置 1 和人 2,导致排列 (2, 1, 3, 4).
- 交换 Person 的位置 1 和人 4,导致排列 (4, 2, 3, 1).
- 交换 Person 的位置 2 和人 4,导致排列 (1, 4, 3, 2).
示例输入 2
3 3 1 1 2
示例输出 2
1
这是高桥可能的操作顺序的示例。
- 在 1-st操作,他交换了Person的位置 1 和人 3,导致排列 (3, 2, 1).
在 2-nd操作,他交换了Person的位置 2 和人 3,导致排列 (2, 3, 1).
在 3-rd操作,他交换了Person的位置 1 和人 3,导致排列 (2, 1, 3).
请注意,在操作序列中,颜色 i前面第一个人的穿着不一定符合 c_i.
示例输入 3
10 4 2 7 1 8 2 8 1 8 2 8
示例输出 3
132