We have a sequence of N integers $A= A_0,A_1, \cdots,~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≤i<j≤K \times N−1)$ such that $B_i>B_j$.
Input is given from Standard Input in the following format:
1 | N K |
Print the inversion number of B, modulo 109+7.
1 | 2 2 |
1 | 3 |
In this case, B=2,1,2,1. We have:
Thus, the inversion number of $B$ is 3.
1 | 3 5 |
1 | 0 |
A may contain multiple occurrences of the same number.
1 | 10 998244353 |
1 | 185297239 |
Be sure to print the output modulo $10^9+7$.
The answer of the problem has a regular pattern.
For example, there is a sequence A and for number $A_n$ in A, the number that is bigger than $A_n$ has two parts: the part before $A_n$ and the part after $A_n$. We copy A for K times.
Firstly, we deal with the back part. If the first A has B numbers bigger than $A_n$ and after $A_n$, it’s the same to the rest K-1 sequences. So for the first $A_n$, it has $B \times K$ pairs. And the second A, it has $B \times (K - 1)$ numbers. $\cdots$. Until the last $A_n$, it has B pairs. So the total answer for the pairs after $A_n$ is $B \times (K + (K - 1) + \cdots + 1) = B \times \frac{K \times (K + 1)}{2}$
Secondly, we deal with the front part. It’s the same to the back part. So I’ll just give an formula here. The answer for the pairs before $A_n$ is $F \times ((K - 1) + (K - 2) +\dots+1) = F \times \frac{K \times (K - 1)}{2}$ . F is the number of numbers that bigger than $A_n$ and before $A_n$.
This is only for one $A_n$. You need to traverse A to find all answers. Add the front part and the back part together and don’t forget to modulo $10^9+7$.
1 |
|