/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
(1,2,\dots,N) の順列 P と整数 K が与えられます。
順列 P に以下の操作を行った後の転倒数の期待値を \text{mod} \ 998244353 で求めてください。
- まず、整数 i を 1 以上 N-K+1 以下の整数の中から一様ランダムに選択する。
- その後、 P_i,P_{i+1},\dots,P_{i+K-1} を一様ランダムにシャッフルする。
転倒数とは?
数列 (A_1,A_2,\dots,A_N) の転倒数とは、 1 \le i < j \le N かつ A_i > A_j を満たす整数組 (i,j) の個数を指します。期待値 \text{mod} \ 998244353 とは?
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。制約
- 入力は全て整数
- 1 \le K \le N \le 2 \times 10^5
- P は (1,2,\dots,N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N K P_1 P_2 \dots P_N
出力
答えを 1 行に出力せよ。
入力例 1
4 2 1 4 2 3
出力例 1
166374061
操作によって、順列 P は以下のように変化します。
- (1,4,2,3) ... 確率 1/2
- (4,1,2,3) ... 確率 1/6
- (1,2,4,3) ... 確率 1/6
- (1,4,3,2) ... 確率 1/6
転倒数の期待値は、 \displaystyle 2 \times \frac{1}{2} + 3 \times \frac{1}{6} + 1 \times \frac{1}{6} + 3 \times \frac{1}{6} = \frac{13}{6} となります。
\displaystyle \frac{13}{6} を \text{mod} \ 998244353 で表現すると 166374061 となるので、これを出力してください。
入力例 2
1 1 1
出力例 2
0
入力例 3
10 6 7 4 10 5 6 1 8 2 3 9
出力例 3
499122200
Score : 575 points
Problem Statement
You are given a permutation P of (1,2,\dots,N) and an integer K.
Find the expected value, modulo 998244353, of the inversion number of P after performing the following operation:
- First, choose an integer i uniformly at random between 1 and N - K + 1, inclusive.
- Then, shuffle P_i, P_{i+1}, \dots, P_{i+K-1} uniformly at random.
What is the inversion number?
The inversion number of a sequence (A_1, A_2, \dots, A_N) is the number of integer pairs (i, j) satisfying 1 \le i < j \le N and A_i > A_j.What does "expected value modulo 998244353" mean?
It can be proved that the sought expected value is always rational. Under the constraints of this problem, when this value is represented as an irreducible fraction \frac{P}{Q}, it can also be proved that Q \not\equiv 0 \pmod{998244353}. Thus, there is a unique integer R satisfying R \times Q \equiv P \pmod{998244353}, \ 0 \le R < 998244353. Report this integer R.Constraints
- All input values are integers.
- 1 \le K \le N \le 2 \times 10^5
- P is a permutation of (1,2,\dots,N).
Input
The input is given from Standard Input in the following format:
N K P_1 P_2 \dots P_N
Output
Print the answer in one line.
Sample Input 1
4 2 1 4 2 3
Sample Output 1
166374061
The operation changes the permutation P into the following:
- (1,4,2,3) ... probability 1/2
- (4,1,2,3) ... probability 1/6
- (1,2,4,3) ... probability 1/6
- (1,4,3,2) ... probability 1/6
The expected value of the inversion number is \displaystyle 2 \times \frac{1}{2} + 3 \times \frac{1}{6} + 1 \times \frac{1}{6} + 3 \times \frac{1}{6} = \frac{13}{6}.
\displaystyle \frac{13}{6} modulo 998244353 is 166374061, so print this number.
Sample Input 2
1 1 1
Sample Output 2
0
Sample Input 3
10 6 7 4 10 5 6 1 8 2 3 9
Sample Output 3
499122200