分数: 1500 点
问题陈述
给你整数 N 和 K,以及排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).
您可以执行以下操作任意次数,可能为零。
- 选择一个整数 i (1 \leq i \leq N-K+1)。 交换两个最大元素的值 P_i,P_{i+1},\cdots,P_{i+K-1}.
求模数 998244353,在你的操作之后,可以得到的排列。 P 。 在这种情况下,该操作只能与
约束
- 2 \leq K \leq N \leq 250000
- (P_1,P_2,\cdots,P_N) 是一个排列 (1,2,\cdots,N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \cdots P_N
输出
打印答案。
示例输入 1
3 3 2 3 1
示例输出 1
2
一起执行。 i=1.
一次操作后,两个最大元素 P_1,P_2,P_3,它们是 P_2=3 和 P_1=2的值会被交换,你有 P=(3,2,1)。 再进行一次操作后,你将有 P=(2,3,1).
因此,有两个排列, P=(2,3,1),(3,2,1),即 P 。 在这种情况下,该操作只能与
示例输入 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
1451520