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