AT_arc154_e.[ARC154E] Reverse and Inversion

对于 $ (1,2,\dots,N) $ 的一个排列 $ Q=(Q_1,Q_2,\dots,Q_N) $，定义如下的值为 $ f(Q) $：

对于所有满足 $ 1\leq i < j \leq n$ 且 $ Q_i > Q_j $ 的整数对 $ (i,j) $，将所有 $ j-i $ 的和记为 $ f(Q) $。

给定 $ (1,2,\dots,N) $ 的一个排列 $ P=(P_1,P_2,\dots,P_N) $。

你需要重复以下操作 $ M $ 次：

• 选择满足 $ 1\leq i\leq j\leq N $ 的一组整数 $ (i,j) $。将 $ P_i,P_{i+1},\dots,P_j $ 反转。更具体地说，将 $ P_i,P_{i+1},\dots,P_j $ 的值同时替换为 $ P_j,P_{j-1},\dots,P_i $。

操作的选择方式共有 $ \left(\frac{N(N+1)}{2}\right)^M $ 种。对于所有这些操作结束后的 $ f(P) $，你需要求它们的总和，并对 $ 998244353 $ 取模。

输入以如下格式从标准输入给出。

$ N $ $ M $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

输出一行，表示答案。

限制条件

• $ 1\leq N,M\leq 2\times 10^5 $
• $ (P_1,P_2,\dots,P_N) $ 是 $ (1,2,\dots,N) $ 的一个排列。

样例解释 1

所有可能的操作如下，共有 $ 3 $ 种：

• 选择 $ (i,j)=(1,1) $。此时 $ P=(1,2) $，$ f(P)=0 $。
• 选择 $ (i,j)=(1,2) $。此时 $ P=(2,1) $，$ f(P)=1 $。
• 选择 $ (i,j)=(2,2) $。此时 $ P=(1,2) $，$ f(P)=0 $。

因此，答案为 $ 0+1+0=1 $。

由 ChatGPT 4.1 翻译