题解：AT_jsc2019_qual_b Kleene Inversion

思路：

因为共有

k

段

A

序列，所以逆序对分为两种：

在不同的 $A$ 序列中。
在相同的 $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:

CPP

#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;
}

~~易如反掌~~

题解：AT_jsc2019_qual_b Kleene Inversion

文章操作

思路：

Code:

相关推荐

评论

题解：AT_jsc2019_qual_b Kleene Inversion