JCP选拔赛C Cell Inversion

这是一个atcoder上选拔赛的题2333

URL: Atcoder

题面描述

给出一个a数组,把这个数组重复k遍,求有几个正序对,k很大

思路

枚举a数组中元素,计算有这个元素的正序对个数,然后乘上$\frac{k\times(k+1)}{2}$再减去这个元素的逆序对个数乘k,将结果加上ans即可

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,k,a[2005];
long long kk2,kk,cnt1=0,cnt2=0;
unsigned long long ans=0;
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
kk=(k*(k+1)/2)%mod;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
cnt1=0,cnt2=0;
for(int j=0;j<n;j++){
if(a[i]>a[j]) cnt1++;
if(a[i]>a[j]&&j<i) cnt2++;
}
ans+=mod;
ans+=(cnt1*kk%mod-k*cnt2)%mod;
ans%=mod;
}
cout<<ans;
return 0;
}