AT_agc030_d [AGC030D] Inversion Sum题解

#include<bits/stdc++.h>

using namespace std;

namespace LYY_XPLOR {
	#define int long long 
	#define F(i, a, b) for(int i = a; i <= b; i ++ )
	#define dF(i, a, b) for(int i = a; i >= b; i -- )
	#define eF(i, a) for(int i = h[a]; ~i; i = ne[i])
	#define ll long long 
	#define ull unsigned long long
	#define db double
	#define ldb long double
	#define pii pair<int, int>
	#define pb push_back
	#define MP make_pair
	#define N 3010
	#define inv 500000004
	#define mod 1000000007

	int qmi(int a, int b) {int res = 1;while(b) {if(b & 1) res = res * a % mod;b >>= 1;a = a * a % mod;}return res;}
	int n, q;
	int a[N], f[N][N];
	int X[N], Y[N];
	signed main() {
		scanf("%lld%lld", &n, &q);
		F(i, 1, n) scanf("%d", a + i);
		F(i, 1, n) F(j, 1, n) f[i][j] = (a[i] < a[j]);
		F(i, 1, q) {
			int u, v;
			scanf("%d%d", &u, &v);
			F(i, 1, n) if(i != u && i != v) f[u][i] = f[v][i] = (f[u][i] + f[v][i]) % mod * inv % mod;
			F(i, 1, n) if(i != u && i != v) f[i][u] = f[i][v] = (f[i][v] + f[i][u]) % mod * inv % mod;
			f[u][v] = f[v][u] = (f[u][v] + f[v][u]) % mod * inv % mod;
		} 
		
		int ans = 0;
		F(i, 1, n) F(j, 1, i - 1) ans = (ans + f[i][j]) % mod; 
		ans = ans * qmi(2, q) % mod;
		printf("%lld\n", ans);
		return 0;
	}	
}

signed main() {
	LYY_XPLOR::main();
	return 0;
}