AT_agc054_c [AGC054C] Roughly Sorted

题目描述

すぬけくん得到了一个 $(1,\ 2,\ ...,\ N)$ 的排列 $P=(P_1,P_2,\cdots,P_N)$ 和一个整数 $K$。于是，すぬけくん不断交换 $P$ 中相邻的两个元素，使得满足以下条件：

• 对于每个 $1\leq i\leq N$，满足 $1\leq j<i$ 且 $P_j>P_i$ 的 $j$ 的个数至多为 $K$。

在这里，すぬけくん以最小的操作次数达成了上述条件。

所有操作结束后，すぬけくん忘记了原来的排列。现在给定操作后的排列 $P'$，请你求出有多少种可能的原始排列 $P$，使得经过最小次数的相邻交换后可以得到 $P'$，并将答案对 $998244353$ 取模。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案。

样例 1

输入

3 1
3 1 2

输出

2

样例 2

输入

4 3
4 3 2 1

输出

1

样例 3

输入

5 2
4 2 1 5 3

输出

3

说明/提示

限制条件

• $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$，满足 $1\leq j<i$ 且 $P'_j>P'_i$ 的 $j$ 的个数至多为 $K$。
• 输入的所有值均为整数。

样例解释 1

作为 $P$ 的可能有以下 $2$ 种情况：

• $P=(3,1,2)$：最小操作次数为 $0$，操作后的排列与 $P'$ 相同。
• $P=(3,2,1)$：最小操作次数为 $1$，交换 $P_2$ 和 $P_3$ 后得到 $P=(3,1,2)$，满足条件，操作后的排列与 $P'$ 相同。

由 ChatGPT 4.1 翻译