Codeforces ECR #057 : F. Inversion Expectation

なんか見たことあるなぁ…。
https://codeforces.com/contest/1096/problem/F

問題

1～NのPermutationが与えられる。ただし一部の要素は未確定である。
未確定の要素に、残った数字が等確率で埋まるとき、転倒数の期待値を求めよ。

解法

確定済みの要素の転倒数はBITで求められる。
未確定同士の要素は、1/2の確率で転送数1が生じる。

あとは、確定済みの要素毎に、その前の要素に自身より大きな値が入る確率と、後の要素に自身より小さな値が入る確率をそれぞれBIT等で数え上げ、総和を取ればよい。
おそらく、逆に未確定要素を辿っても解けるはず。

int N;
int A[202020];
ll mo=998244353;

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

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>>N;
	
	int uns=N;
	ll ret=0;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]>=0) {
			ret+=bt(N)-bt(A[i]);
			bt.add(A[i],1);
		}
	}
	ret%=mo;
	FOR(i,N) {
		bt.add(i+1,1);
		if(A[i]>=0) {
			bt.add(A[i],mo-2);
			uns--;
		}
	}
	(ret+=1LL*uns*(uns-1)%mo*((mo+1)/2)%mo*((mo+1)/2))%=mo;
	x=0;
	FOR(i,N) {
		if(A[i]==-1) {
			x++;
		}
		else if(uns) {
			int larger=bt(N)-bt(A[i]);
			(ret += larger*modpow(uns)%mo*x)%=mo;
			(ret += (uns-larger)*modpow(uns)%mo*(uns-x))%=mo;
		}
	}
	cout<<ret<<endl;
}

まとめ

どこで見たんだろう…。