← 返回题目列表

AtCoder · arc154_e

E. 反转和反转

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

分数: 900 点

问题陈述

对于排列 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N),让 f(Q) 为以下值:

总和 j-i 所有整数对 (i,j) 这样 1 \le i < j \le N 和 Q_i > Q_j.

给你一个排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).

让我们重复以下操作 M 次。

  • 选择一对整数 (i,j) 这样 1 \le i \le j \le N。反向 P_i,P_{i+1},\dots,P_j。正式地,替换以下值 P_i,P_{i+1},\dots,P_j 与 P_j,P_{j-1},\dots,P_i 同时进行。

有 \left(\frac{N(N+1)}{2}\right)^{M} 方式重复操作。假设我们已经计算了 f(P) 对于所有这些方式。

求这些的总和 \left(\frac{N(N+1)}{2}\right)^{M} 值,模数 998244353.

约束

  • 1 \le N,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

2 1
1 2

示例输出 1

1

执行该操作的方法有以下三种。

  • 选择 (i,j)=(1,1), 制作 P=(1,2),其中 f(P)=0.
  • 选择 (i,j)=(1,2), 制作 P=(2,1),其中 f(P)=1.
  • 选择 (i,j)=(2,2), 制作 P=(1,2),其中 f(P)=0.

因此,答案是 0+1+0=1.


示例输入 2

3 2
3 2 1

示例输出 2

90

示例输入 3

10 2023
5 8 1 9 3 10 4 7 2 6

示例输出 3

543960046