← 返回题目列表

AtCoder · abc247_h

Ex. 重新排列问题

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

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