B - Kleene Inversion

Contest Duration: 2019-08-24(Sat) 12:00 - 2019-08-24(Sat) 13:40 (local time) (100 minutes) Back to Home

B - Kleene Inversion Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $300$ 点

問題文

長さ $N$ の整数列 $A~=~A_0,~A_1,~...,~A_{N - 1}$ があります。

$A$ を $K$ 回繰り返した長さ $K \times N$ の整数列を $B$ とします。たとえば $A~=~1,~3,~2$ 、 $K~=~2$ のとき、 $B~=~1,~3,~2,~1,~3,~2$ です。

$B$ の転倒数を $10^9 + 7$ で割った余りを求めてください。

ここで $B$ の転倒数は、整数の順序対 $(i,~j)~(0 \leq i < j \leq K \times N - 1)$ であって $B_i > B_j$ を満たすものの個数として定義されます。

制約

入力は全て整数である。
$1 \leq N \leq 2000$
$1 \leq K \leq 10^9$
$1 \leq A_i \leq 2000$

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $K$ 
 $A_0$   $A_1$   $...$   $A_{N - 1}$

出力

$B$ の転倒数を $10^9 + 7$ で割った余りを出力せよ。

入力例 1Copy

Copy

2 2
2 1

出力例 1Copy

Copy

このケースでは $B~=~2,~1,~2,~1$ です。

$B_0 > B_1$
$B_0 > B_3$
$B_2 > B_3$

であり、 $B$ の転倒数は $3$ です。

入力例 2Copy

Copy

3 5
1 1 1

出力例 2Copy

Copy

$A$ は同じ数を複数含むこともあります。

入力例 3Copy

Copy

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

出力例 3Copy

Copy

185297239

$10^9 + 7$ で割った余りを出力することに注意してください。

Score : $300$ points

Problem Statement

We have a sequence of $N$ integers $A~=~A_0,~A_1,~...,~A_{N - 1}$ .

Let $B$ be a sequence of $K \times N$ integers obtained by concatenating $K$ copies of $A$ . For example, if $A~=~1,~3,~2$ and $K~=~2$ , $B~=~1,~3,~2,~1,~3,~2$ .

Find the inversion number of $B$ , modulo $10^9 + 7$ .

Here the inversion number of $B$ is defined as the number of ordered pairs of integers $(i,~j)~(0 \leq i < j \leq K \times N - 1)$ such that $B_i > B_j$ .

Constraints

All values in input are integers.
$1 \leq N \leq 2000$
$1 \leq K \leq 10^9$
$1 \leq A_i \leq 2000$

Input

Input is given from Standard Input in the following format:

 $N$   $K$ 
 $A_0$   $A_1$   $...$   $A_{N - 1}$

Output

Print the inversion number of $B$ , modulo $10^9 + 7$ .

Sample Input 1Copy

Copy

2 2
2 1

Sample Output 1Copy

Copy

In this case, $B~=~2,~1,~2,~1$ . We have:

$B_0 > B_1$
$B_0 > B_3$
$B_2 > B_3$

Thus, the inversion number of $B$ is $3$ .

Sample Input 2Copy

Copy

3 5
1 1 1

Sample Output 2Copy

Copy

$A$ may contain multiple occurrences of the same number.

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy

185297239

Be sure to print the output modulo $10^9 + 7$ .