分数: 900 点
问题陈述
给定一个排列 p_1, p_2, \dots, p_N of (1, 2, ..., N) 和一个整数 K。 Maroon 执行以下操作 i = 1, 2, \dots, N - K + 1 按此顺序:
- 随机播放 p_i, p_{i + 1}, \dots, p_{i + K - 1} 均匀随机。
求所有运算完成后数列的反转数的期望值,并取模打印 998244353.
更具体地说,从这个问题的约束来看,可以证明期望值始终是一个有理数,可以表示为一个不可约分数 \frac{P}{Q},并且整数 R 满足 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 是唯一确定的。打印此内容 R.
这里,序列的反转数 a_1, a_2, \dots, a_N 被定义为有序对的数量 (i, j) 满足 i < j, a_i > a_j.
约束
- 2 \leq N \leq 200,000
- 2 \leq K \leq N
- (p_1, p_2, \dots, p_N) 是一个排列 (1, 2, \dots, N).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K p_1 p_2 ... p_N
输出
打印期望值模 998244353.
示例输入 1
3 2 1 2 3
示例输出 1
1
最终序列是以下之一 (1, 2, 3), (2, 1, 3), (1, 3, 2), (2, 3, 1),每个都有概率 \frac{1}{4}。 他们的反转数是 0, 1, 1, 2 分别,所以期望值为 1.
示例输入 2
10 3 1 8 4 9 2 3 7 10 5 6
示例输出 2
164091855