← 返回题目列表

AtCoder · agc054_c

C. 粗略排序

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

分数: 800 点

问题陈述

Snuke 收到了排列 P=(P_1,P_2,\cdots,P_N) of (1,\ 2,\ ...\ N) 和一个整数 K。 他对两个相邻元素进行了一些交换 P 以便满足以下条件。

  • 对于每个 1 \leq i \leq N,最多有 K 指数 j 这样 1 \leq j< i 和 P_j>P_i.

在这里,他做了 最小值 达到此条件所需的交换次数。

之后,他忘记了他收到的原始排列。 给定排列 P' 交换后,找到数字,模 998244353,原始排列的排列 P 可能是。

约束

  • 2 \leq N \leq 5000
  • 1 \leq K \leq N-1
  • 1 \leq P'_i \leq N
  • P'_i \neq P'_j (i \neq j)
  • 对于每个 1 \leq i \leq N,最多有 K 指数 j 这样 1 \leq j< i 和 P'_j>P'_i.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
P'_1 P'_2 \cdots P'_N

输出

打印答案。


示例输入 1

3 1
3 1 2

示例输出 1

2

P 可以是以下两种排列之一。

  • P=(3,1,2):所需的最小交换次数为 0。零交换后,排列等于 P'.
  • P=(3,2,1):所需的最小交换次数为 1:交换 P_2 和 P_3 结果 P=(3,1,2),满足条件并且等于 P'.

示例输入 2

4 3
4 3 2 1

示例输出 2

1

示例输入 3

5 2
4 2 1 5 3

示例输出 3

3