AT_abc247_h [ABC247Ex] Rearranging Problem

题目描述

有 $N$ 个人，编号为 $1, 2, \dots, N$，他们按照 $(1,2,\dots,N)$ 的顺序排成一列。第 $i$ 个人穿着颜色为 $c_i$ 的衣服。
高桥君进行了 $K$ 次操作，每次操作可以任选两个人 $i, j$，交换他们的位置。
在 $K$ 次操作结束后，对于所有满足 $1 \leq i \leq N$ 的整数 $i$，从前往后第 $i$ 个人所穿的衣服颜色都与 $c_i$ 一致。
请问在 $K$ 次操作结束后，可能出现多少种不同的人的排列方式？请将答案对 $998244353$ 取模后输出。

输入格式

输入以如下格式从标准输入中给出。

$N$ $K$ $c_1$ $c_2$ $\dots$ $c_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 1
1 1 2 1

输出 #1

3

输入输出样例 #2

输入 #2

3 3
1 1 2

输出 #2

1

输入输出样例 #3

输入 #3

10 4
2 7 1 8 2 8 1 8 2 8

输出 #3

132

说明/提示

限制条件

• $2 \leq N \leq 200000$
• $1 \leq K \leq 10^9$
• $1 \leq c_i \leq N$
• 输入的所有数均为整数。

样例解释 1

高桥君的操作以及操作后可能的排列如下所示。

• 将第 $1$ 个人和第 $2$ 个人交换位置。操作后排列为 $(2, 1, 3, 4)$。
• 将第 $1$ 个人和第 $4$ 个人交换位置。操作后排列为 $(4, 2, 3, 1)$。
• 将第 $2$ 个人和第 $4$ 个人交换位置。操作后排列为 $(1, 4, 3, 2)$。

样例解释 2

举一个可能的高桥君的操作例子如下。

• 第 $1$ 次操作，将第 $1$ 个人和第 $3$ 个人交换位置。操作后排列为 $(3, 2, 1)$。
• 第 $2$ 次操作，将第 $2$ 个人和第 $3$ 个人交换位置。操作后排列为 $(2, 3, 1)$。
• 第 $3$ 次操作，将第 $1$ 个人和第 $3$ 个人交换位置。操作后排列为 $(2, 1, 3)$。 请注意，在操作过程中，从前往后第 $i$ 个人的衣服颜色不一定始终与 $c_i$ 一致。

由 ChatGPT 4.1 翻译