yukicoder : No.2336 Do you like typical problems?

これはどうにか。
https://yukicoder.me/problems/no/2336

問題

長さNの整数列Aを考える。
A[i]は、[L[i],R[i]]の範囲は等確率で選ばれる、という条件が与えられる。

この区間の並べ替え方N!通りにおいて、転倒数の期待値の総和を求めよ。

解法

先にA[i]を定めて、その後N!通り並べ替えることを考える。
ある2要素A[i],A[j]は、基本的にN!通り考えると1/2のケースで転倒することになる。
例外はA[i]=A[j]のケースである。

よって、A[i]=A[j]となるケースを数え上げよう。
入力を座標圧縮すると、各区間に各要素がどれだけの確率で選ばれるかがわかる。
それらの情報について、2要素の確率の積を計算していくとよい。

int N;
int B[202020],C[202020];

vector<int> add[404040];
vector<int> del[404040];
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>>N;
	vector<int> Xs={0};
	FOR(i,N) {
		cin>>B[i]>>C[i];
		C[i]++;
		Xs.push_back(B[i]);
		Xs.push_back(C[i]);
	}
	sort(ALL(Xs));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	
	FOR(i,N) {
		x=lower_bound(ALL(Xs),B[i])-Xs.begin();
		y=lower_bound(ALL(Xs),C[i])-Xs.begin();
		add[x].push_back(modpow(C[i]-B[i]));
		del[y].push_back(modpow(C[i]-B[i]));
	}
	
	ll ret=1LL*N*(N-1)%mo*modpow(4)%mo;
	ll sum1=0,sum2=0;
	FOR(i,Xs.size()) {
		FORR(d,del[i]) {
			(sum1+=mo-d)%=mo;
			(sum2+=mo-sum1*d)%=mo;
		}
		FORR(d,add[i]) {
			(sum2+=sum1*d)%=mo;
			(sum1+=d)%=mo;
		}
		if(sum2) {
			(ret+=mo-sum2*(Xs[i+1]-Xs[i])%mo*modpow(2)%mo)%=mo;
		}
	}
	FOR(i,N) ret=ret*(i+1)%mo;
	cout<<ret<<endl;
}

まとめ

ちょっと手間取ったけどどうにかなってよかった。