Codeforces #388 Div2 E. Inversions After Shuffle

本番は状態遷移が混乱して間に合わず。
http://codeforces.com/contest/749/problem/E

問題

1～NのPermutation Aがある。
このうち連続部分列のとり方はN*(N+1)/2通りある。
連続部分列のうち１つを等確率で選び、その中を均等な確率でシャッフルすることを考える。

シャッフル後の反転数の期待値を求めよ。

解法

Editorialよりもコメント欄の方がわかりやすい。

長さLの相異なる数値からなる配列をシャッフルすると、反転数はである。
inv(a,b)をA[a...b]の反転数とする。
区間[L...R]をシャッフルした場合の反転数を考えると、求める解は}{\frac{N(N+1)}{2}}]である。

inv(1,N)はBITを使い元のAの反転数を求めればよい。シャッフル後の反転数の総和も反転する範囲の長さがそれぞれ何回登場するか考えればわかる。
あとはinv(L,R)の総和を求めていく。

LをNから1に向けて動かし、Lに対するinv(L,*)の総和を求めていこう。
A[(L+1)...N]の間に、A[L]＞A[x]となるxがあったとすると、inv(L,x)～inv(L,N)の間に反転数が1加算される。
この処理を高速に済ませるには、A[(L+1)...N]に関し、BITを用いて、添え字A[x]に対し(N-x+1)を加算しておけば、BITにおいて添え字1～A[L]の値の総和を取ればよい。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;

ll N;
ll A[101010];
long double ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	// inside perm;
	ll pat=0;
	for(ll len=1;len<=N;len++) {
		pat += N+1-len;
		ret += (N+1.0-len) * len*(len-1)/4;
	}
	for(i=N-1;i>=0;i--) {
		ret += pat*bt(A[i]);
		bt.add(A[i],1);
	}
	FOR(i,N) bt.add(A[i],-1);
	
	ll inv=0;
	for(i=N-1;i>=0;i--) {
		inv += bt(A[i]);
		ret -= inv;
		bt.add(A[i],N-i);
	}
	
	_P("%.12lf\n",(double)(ret/pat));
}

まとめ

こういう数え上げをすんなり解けるようになりたい。