分数: 700 点
问题陈述
给你一个排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N)。您将执行以下操作 M 次:
- 选择一对整数 (i, j) 这样 1 \le i < j \le N,并交换 P_i 和 P_j.
有 \left(\frac{N(N-1)}{2}\right)^M 可能的操作顺序。对于它们中的每一个,考虑其值 \sum_{i=1}^{N-1} |P_i - P_{i+1}| 完成所有操作后。求总和,取模 998244353,所有这些值。
约束
- 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).
输入
输入由标准输入按以下格式给出:
N M P_1 P_2 \dots P_N
输出
打印答案。
示例输入 1
3 1 1 3 2
示例输出 1
8
存在三种可能的操作顺序:
- 选择 (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.
示例输入 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