#P13626. [ARC176D] Swap Permutation

    ID: 12828 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-贡献法交换求和顺序线性 DP线性递推等差数列求和

[ARC176D] Swap Permutation

题目描述

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

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

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

输入格式

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

N N M M P1 P_1 P2 P_2 … \dots PN P_N

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 1
1 3 2

输出 #1

8

输入输出样例 #2

输入 #2

2 5
2 1

输出 #2

1

输入输出样例 #3

输入 #3

5 2
3 5 1 4 2

输出 #3

833

输入输出样例 #4

输入 #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≤N≤2×105 2\le N\le 2\times 10^5
  • 1≤M≤2×105 1\le M\le 2\times 10^5
  • (P1,P2,…,PN) (P_1,P_2,\dots,P_N) 是 (1,2,…,N) (1,2,\dots,N) 的一个排列

样例解释 1

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

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

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