题解：AT_jsc2019_qual_b Kleene Inversion

dulinfan2023 · 2024-12-21 12:22:45 · 题解

思路：

因为共有 k 段 A 序列，所以逆序对分为两种：

1. 在不同的 A 序列中。
2. 在相同的 A 序列中。

第 1 种情况就是求出 1 \le i \le n，1 \le j \le n，a_i>a_j 组成的数对的个数乘上 \frac{k\times(k-1)}{2}，表示对于所有第 l 个序列和第 r 个序列组成的数对，保证 1 \le l \le r \le k。

第 2 种情况就是在所有 k 个序列中的逆序对，共有 A 序列的逆序对个数乘上 k。

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
int n,a[2005],k,s,ss;
const int mod=1e9+7;
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[j]>a[i])s++,s%=mod;
        }
    }
    int kk=k*(k-1)/2;
    kk%=mod;
    s*=kk;
    s%=mod;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i])ss++;
        }
    }
//  cout<<s<<" "<<kk<<" "<<ss<<" "<<k<<'\n';
    cout<<(s+ss*k%mod)%mod;
}

易如反掌