题目链接
思路
看一眼题目数据，就知道肯定不能 \(brute-force\) ，所以我们要考虑优化。
首先不难发现，所有逆序对的数量 \(=\) \(k\) 组里的逆序对数量 \(+\) 跨组的逆序对数量，第一个很好求，暴力求出逆序对数量，再乘上 \(k\) 就好了，我们重点看第二个怎么求：
首先，任意两个组的逆序对数量一定是不变的，所以我们可以通过求两组数的逆序对数量乘上有几种方法来选两组，求两组数量的逆序对数量直接暴力求出来就好了，要注意减掉不跨组的逆序对数量，那我们该怎么求能有几种方法来选两组呢？第一组可以跟后面 \(k - 1\) 组组合，第二组可以跟后面 \(k - 2\) 组组和，以此类推，最终一共有 \(1+2+...+(k-1)+k=(k - 1) \times k \div 2\) ，由于除以 \(2\) 可能除不尽，所以要成上 \(2\) 的逆元就好了，由于 \(1e9+7\) 是质数，所以可以用快速幂求逆元，这里阐述有些拗口，可以结合代码理解。
不用特判 \(k = 1\) 的情况！还要注意取模：多模几次不会错，少模几次容易爆掉 \(long~long\) ！
代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 4010,MOD = 1e9 + 7;
int n,k;
int a[N],b[N];
LL power (LL a,LL b,LL p) {
LL ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int main () {
cin >> n >> k;
for (int i = 1;i <= n;i++) {
cin >> a[i];
b[i] = b[i + n] = a[i];
}
LL cnt1 = 0,cnt2 = 0;
for (int i = 1;i <= n;i++) {
for (int j = i + 1;j <= n;j++) {
if (a[i] > a[j]) cnt1++;
}
}
if (k == 1) {
cout << cnt1 % MOD << endl;
return 0;
}
for (int i = 1;i <= 2 * n;i++) {
for (int j = i + 1;j <= 2 * n;j++) {
if (b[i] > b[j]) cnt2++;
}
}
cnt2 -= cnt1 * 2;
cout << (cnt2 * (k - 1) % MOD * k % MOD * power (2,MOD - 2,MOD) % MOD + cnt1 * k) % MOD << endl;
return 0;
}