/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
(1,2,\dots,N) の順列 Q=(Q_1,Q_2,\dots,Q_N) に対する以下の値を f(Q) と置きます。
1 \le i < j \le N かつ Q_i > Q_j を満たす整数の組 (i,j) 全てに対する j-i の総和
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) が与えられます。
以下の操作を M 回繰り返します。
- 1 \le i \le j \le N を満たす整数の組 (i,j) を選ぶ。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 行に出力せよ。
入力例 1
2 1 1 2
出力例 1
1
あり得る操作は以下の 3 通りです。
- (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
Score : 900 points
Problem Statement
For a permutation Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N), let f(Q) be the following value:
the sum of j-i over all pairs of integers (i,j) such that 1 \le i < j \le N and Q_i > Q_j.
You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
Let us repeat the following operation M times.
- Choose a pair of integers (i,j) such that 1 \le i \le j \le N. Reverse P_i,P_{i+1},\dots,P_j. Formally, replace the values of P_i,P_{i+1},\dots,P_j with P_j,P_{j-1},\dots,P_i simultaneously.
There are \left(\frac{N(N+1)}{2}\right)^{M} ways to repeat the operation. Assume that we have computed f(P) for all those ways.
Find the sum of these \left(\frac{N(N+1)}{2}\right)^{M} values, modulo 998244353.
Constraints
- 1 \le N,M \le 2 \times 10^5
- (P_1,P_2,\dots,P_N) is a permutation of (1,2,\dots,N).
Input
The input is given from Standard Input in the following format:
N M P_1 P_2 \dots P_N
Output
Print a single line containing the answer.
Sample Input 1
2 1 1 2
Sample Output 1
1
There are three ways to perform the operation, as follows.
- Choose (i,j)=(1,1), making P=(1,2), where f(P)=0.
- Choose (i,j)=(1,2), making P=(2,1), where f(P)=1.
- Choose (i,j)=(2,2), making P=(1,2), where f(P)=0.
Thus, the answer is 0+1+0=1.
Sample Input 2
3 2 3 2 1
Sample Output 2
90
Sample Input 3
10 2023 5 8 1 9 3 10 4 7 2 6
Sample Output 3
543960046