← 返回题目列表

AtCoder · arc176_d

D. 交换排列

中文机器翻译题面 查看原题

分数: 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