AT_arc176_d [ARC176D] Swap Permutation

题目描述

给定一个 $(1,2,\dots,N)$ 的排列 $P=(P_1,P_2,\dots,P_N)$。接下来要进行 $M$ 次如下操作：

• 选择满足 $1\le i<j\le N$ 的整数对 $(i,j)$，交换 $P_i$ 和 $P_j$。

操作序列共有 $\left(\frac{N(N-1)}{2}\right)^M$ 种。请你求出所有操作序列结束后 $\sum_{i=1}^{N-1} |P_i - P_{i+1}|$ 的总和对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出答案。

样例 1

输入

3 1
1 3 2

输出

8

样例 2

输入

2 5
2 1

输出

1

样例 3

输入

5 2
3 5 1 4 2

输出

833

样例 4

输入

20 24
14 1 20 6 11 3 19 2 7 10 9 18 13 12 17 8 15 5 4 16

输出

203984325

说明/提示

限制条件

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

样例解释 1

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

• 选择 $(i,j) = (1,2)$，$P=(3,1,2)$。
• 选择 $(i,j) = (1,3)$，$P=(2,3,1)$。
• 选择 $(i,j) = (2,3)$，$P=(1,2,3)$。

对应的 $\sum_{i=1}^{N-1} |P_i - P_{i+1}|$ 分别为 $3,3,2$。因此答案为 $3+3+2=8$。

由 ChatGPT 4.1 翻译