AtCoder AGC #030 : D - Inversion Sum

発想が足りなさすぎる…。
https://atcoder.jp/contests/agc030/tasks/agc030_d

問題

N要素の数列Aが与えられる。
ここにQ個のクエリが与えられる。
各クエリはindexの対i,jで構成され、AiとAjをスワップすることを意味する。

各クエリについて、順次適用する場合としない場合を考えると合計2^Q通りの組み合わせが考えられる。
それぞれにおける転倒数の総和を求めよ。

解法

各クエリ、1/2の確率で適用する、と考え、最後に転倒数の期待値に2^Qをかけてもよい。
よってこの期待値を求めよう。

自分がやって最初失敗したのが、最初A[i]にあった要素が、最後にA[j]に行く確率P(i,j)を求める、というものである。
ただ今回の問題設定では、各確率が独立でないためこれではうまくいかない。

そこでP(x,y) := A[x]＞A[y]である確率、とし、クエリ毎にP(x,y)を更新していこう。
最終的にP(x,y)の総和が求める期待値となる。
1回のクエリで更新すべきは、P(i,*),P(j,*),P(*,i),P(*,j)のO(N)通り程度なので、全体がO(N^2+NQ)で済む。

int N,Q;
int A[3030];
ll mo=1000000007;

ll P[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,N) FOR(j,N) P[i][j]=A[i]>A[j];
	
	FOR(j,Q) {
		cin>>x>>y;
		x--,y--;
		FOR(i,N) {
			if(i!=x && i!=y) {
				P[i][x]=P[i][y]=(P[i][x]+P[i][y])*((mo+1)/2)%mo;
				P[x][i]=P[y][i]=(P[x][i]+P[y][i])*((mo+1)/2)%mo;
			}
		}
		P[x][y]=P[y][x]=(P[x][y]+P[y][x])*((mo+1)/2)%mo;
	}
	
	ll ret=0;
	FOR(i,N) FOR(j,i) ret+=P[j][i];
	ret%=mo;
	FOR(i,Q) ret=ret*2%mo;
	
	cout<<ret<<endl;
}

まとめ

このPを思いつくかがどうかが問題。