「AGC030D」Inversion Sum

妙啊。

由于逆序对的个数最多只有 \(O(n^2)\) 对，而对于每一个询问与其相关的逆序对数也最多只有 \(O(n)\) 对，我们可以对于每一对数分别考虑其贡献。

然后你发现直接算所有情况的和非常麻烦，所以我们可以先算出所有情况的期望逆序对数，即每一对为逆序对的概率之和，然后乘上 \(2^q\)。

那这就非常 easy 了。

就每次对于有关联的两对取一个平均值就完事了。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

const int p=1e9+7;

const int inv2=(p+1)/2;

const int maxn=3e3+5;

int a[maxn];

int f[maxn][maxn];

int ksm(int a,int b,int p){

	int ans=1;

	while(b){

		if(b&1) ans=1ll*ans*a%p;

		b>>=1,a=1ll*a*a%p;

	}

	return ans;

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n,q;cin>>n>>q;

	for(int i=1;i<=n;++i) cin>>a[i];

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			f[i][j]=a[i]>a[j];

	for(int _=1;_<=q;++_){

		int x,y;

		cin>>x>>y;f[x][y]=f[y][x]=1ll*inv2*(f[x][y]+f[y][x])%p;

		for(int i=1;i<=n;++i){

			if(i==x||i==y) continue;

			f[x][i]=f[y][i]=1ll*inv2*(f[x][i]+f[y][i])%p;

			f[i][y]=f[i][x]=1ll*inv2*(f[i][y]+f[i][x])%p;

		}

	}

	int ans=0;

	for(int i=1;i<=n;++i)

		for(int j=i+1;j<=n;++j)

			ans=(ans+f[i][j])%p;

	cout<<1ll*ans*ksm(2,q,p)%p<<'\n';

	return 0;

}

巴特西

「AGC030D」Inversion Sum

「AGC030D」Inversion Sum

最新文章

热门文章