AT_abc380_g.[ABC380G] Another Shuffle Window

问题链接

给定一个排列 $P = (1, 2, \dots, N)$ 和一个整数 $K$。

请计算经过以下操作后，排列 $P$ 的逆序对数的期望值模 $998244353$ 的结果：

• 首先，从 $1$ 到 $N-K+1$ 的整数中随机均匀地选择一个整数 $i$；
• 然后，将子数组 $P_i, P_{i+1}, \dots, P_{i+K-1}$ 进行随机均匀打乱。

逆序对是什么？

对于一个数组 $(A_1, A_2, \dots, A_N)$，逆序对是满足 $1 \leq i < j \leq N$ 且 $A_i > A_j$ 的整数对 $(i, j)$ 的个数。

期望值模 $998244353$ 是什么？

在本问题的约束条件下，期望值可以表示为一个分数 $\frac{P}{Q}$，且 $Q \not \equiv 0 \pmod{998244353}$。
因此可以找到一个唯一的整数 $R$ 满足：

$$R \times Q \equiv P \pmod{998244353}, \quad 0 \leq R < 998244353$$

你需要输出这个整数 $R$。

从标准输入流读入，格式如下：

$$N\ K\ P_1\ P_2\ \dots\ P_N$$

输出在标准输出流，在一行中输出答案。

约束条件

• 所有输入均为整数；
• $1 \leq K \leq N \leq 2 \times 10^5$；
• $P$ 是 $(1, 2, \dots, N)$ 的一个排列。

样例解释 1

通过操作，排列 $P$ 会变为以下形式：

• $(1, 4, 2, 3)$ —— 概率 $\frac{1}{2}$；
• $(4, 1, 2, 3)$ —— 概率 $\frac{1}{6}$；
• $(1, 2, 4, 3)$ —— 概率 $\frac{1}{6}$；
• $(1, 4, 3, 2)$ —— 概率 $\frac{1}{6}$。

对应的逆序对数期望值为：

$$\displaystyle 2 \times \frac{1}{2} + 3 \times \frac{1}{6} + 1 \times \frac{1}{6} + 3 \times \frac{1}{6} = \frac{13}{6}$$

将 $\frac{13}{6}$ 转换为模 $998244353$ 的结果为 $166374061$，因此输出 $166374061$。

Translated By $\mathtt{Mr\_Az}$。