Codeforces #829 : Div1 C. Wish I Knew How to Sort

あれ、これなんでこんなてこずってるんだろ。
https://codeforces.com/contest/1753/problem/C

問題

N文字のバイナリ文字列Aが与えられる。
Aからランダムに2要素A[i]、A[j] (i＜j)を選び、A[i]＞A[j]ならswapできるものとする。
Aがソートされるまでに必要な選択回数の期待値はいくつか。

解法

A中に0がX個、1がY個とする。

選択の際、prefix X個から2要素選ばれたり、suffix Y個から2個選ばれたりするケースは、(結果prefix内またはsuffixないでswapが起きても)どうでも良い。

prefix中に1がZ個、suffix中に0がZ個あったとする。
Zが減るのは、prefix X個中の1と、suffix X個中の0が選ばれるケースで、そのような選び方が成されるとZがデクリメントされる。
Z=0になるまで、所定の選び方が成される確率から選択回数の期待値を求めて足していこう。

int T;
int N,S;
int A[202020],B[202020];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		S=0;
		FOR(i,N) {
			cin>>A[i];
			B[i]=A[i];
		}
		sort(B,B+N);
		int dif=0;
		FOR(i,N) dif+=A[i]>B[i];
		
		if(dif==0) {
			cout<<0<<endl;
			continue;
		}
		
		ll ret=0;
		while(dif) {
			ll pat=1LL*N*(N-1)/2%mo;
			ll ok=1LL*dif*dif%mo;
			
			(ret+=pat*modpow(ok))%=mo;
			dif--;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

もっとすんなり解けてもよさそうだが…。