AT_arc176_d.[ARC176D] Swap Permutation
省选/NOI-
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
给定一个 $ (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
输出#1
8
输入#2
2 5 2 1
输出#2
1
输入#3
5 2 3 5 1 4 2
输出#3
833
输入#4
20 24 14 1 20 6 11 3 19 2 7 10 9 18 13 12 17 8 15 5 4 16
输出#4
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 翻译
输入解题思路，AI测评打分。不知道怎么写?