AT_abc380_g [ABC380G] Another Shuffle Window

[问题链接](https://atcoder.jp/contests/abc380/tasks/abc380_g) 给定一个排列 $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}$](/user/536560)。