AT_wtf22_day2_b.The Greatest Two

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定整数 $N,K$ 和一个 $1$ 到 $N$ 的排列 $P=(P_1,P_2,\cdots,P_N)$ 。

你可以进行任意次数（也可以不进行）的如下操作：

选择一个整数 $i$ （ $1\leq i\leq N-K+1$ ）。将 $P_i,P_{i+1},\cdots,P_{i+K-1}$ 中第 $1$ 大的元素和第 $2$ 大的元素的值交换。

请你求出经过若干次操作后，可能得到的不同排列的个数，对 $998244353$ 取模。

输入格式

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

$N$ $K$ $P_1$ $P_2$ $\cdots$ $P_N$

输出格式

输出答案。

输入输出样例

输入#1
```
3 3
2 3 1
```
输出#1
```
2
```
输入#2
```
3 2
1 3 2
```
输出#2
```
6
```
输入#3
```
10 5
1 2 3 4 5 6 7 8 9 10
```
输出#3
```
144
```

输入#4

20 5
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

输出#4

说明/提示

限制

$2\leq K\leq N\leq 250000$
$(P_1,P_2,\cdots,P_N)$ 是 $1$ 到 $N$ 的一个排列。
所有输入的值均为整数。

样例解释 1

在这个例子中，只能进行 $i=1$ 的操作。操作一次后， $P_1,P_2,P_3$ 中第 $1$ 大的元素（ $=P_2=3$ ）和第 $2$ 大的元素（ $=P_1=2$ ）交换，得到 $P=(3,2,1)$ 。再操作一次，得到 $P=(2,3,1)$ 。因此，操作后可能得到的排列有 $P=(2,3,1),(3,2,1)$ 共 $2$ 种。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页