AT_acl1_e.Shuffle Window

给定一个 $ (1, 2, \dots, N) $ 的排列 $ p_1, p_2, \dots, p_N $ 和一个整数 $ K $。maroon 君会对 $ i = 1, 2, \dots, N - K + 1 $ 依次进行如下操作：

• 将 $ p_i, p_{i+1}, \dots, p_{i+K-1} $ 这 $ K $ 个数进行等概率随机打乱。

请你求出所有操作结束后，数列的逆序对数的期望值，并将结果对 $ 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,\ a_i > a_j $ 的有序对 $ (i, j) $ 的个数。

$ N $ $ K $ $ p_1 $ $ p_2 $ ... $ p_N $

请输出期望值对 $ 998244353 $ 取模后的结果。

限制条件

• $ 2 \leq N \leq 200,!000 $
• $ 2 \leq K \leq N $
• $ (p_1, p_2, \dots, p_N) $ 是 $ (1, 2, \dots, N) $ 的一个排列
• 输入的所有数均为整数。

样例解释 1

最终的数列可能为 $ (1, 2, 3) $、$ (2, 1, 3) $、$ (1, 3, 2) $、$ (2, 3, 1) $，它们出现的概率均为 $ \frac{1}{4} $。这些数列的逆序对数分别为 $ 0, 1, 1, 2 $，因此期望值为 $ 1 $。

由 ChatGPT 4.1 翻译