Codeforces ECR #067 : F. Expected Square Beauty

これは勉強になったかな。
https://codeforces.com/contest/1187/problem/F

問題

　
数列Xに対し、評価値B(X)とは、Xを同じ値が連続する箇所を1つにするような形でいくつかの部分列に分割したときの数とする。

ここで、N要素の数列Xを作ることを考える。
2つの数列L,Rが与えられており、i番目の要素は、[L[i],R[i]]のうちいずれかの値を等確率でとるとする。
B(X)の2乗の期待値を求めよ。

解法

I(i,X)とは、数列XにおいてX[i]==X[i-1]なら1、X[i]!=X[i-1]なら0を取る関数とする。(ただしi==0の時は1)
求めるのはE(B^2(X))=E(B(sum(I(i,X))^2))=sum_i sum_j E(I(i,X)*I(j,X))となる。

• i==jなら、E(I(i,X)*I(j,X)) = E(I(i,X))
• iとjが2以上離れているなら、両者無関係に定まるのでE(I(i,X)*I(j,X))=E(I(i,X))*E(I(j,X))
• iとjが1だけ離れている場合、例えばi+1==jとすると、X[i-1],X[i],X[i+1]の値がどうなるかによりE(I(i,X)*I(j,X))が定まる。
  • これは包除原理で確率を求めることができる。

int N;
int L[202020],R[202020];
ll P[202020];
ll mo=1000000007;

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;
}

ll hoge(int i) {
	if(i==0) return P[1];
	ll t=1-(1-P[i])-(1-P[i+1]);
	int LM=max({L[i-1],L[i],L[i+1]});
	int RM=min({R[i-1],R[i],R[i+1]});
	ll a=R[i]-L[i];
	ll b=R[i+1]-L[i+1];
	ll c=R[i-1]-L[i-1];
	ll d=max(0,RM-LM);
	return (t+d*modpow(a*b%mo*c%mo))%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	FOR(i,N) {
		cin>>R[i];
		R[i]++;
	}
	
	P[0]=1;
	ll PS=1;
	for(i=1;i<N;i++) {
		int LM=max(L[i],L[i-1]);
		int RM=min(R[i],R[i-1]);
		int a=R[i-1]-L[i-1];
		int b=R[i]-L[i];
		int c=max(0,RM-LM);
		ll same=c*modpow(1LL*a*b%mo)%mo;
		P[i]=(1+mo-same)%mo;
		(PS+=P[i])%=mo;
	}
	
	ll ret=PS;
	FOR(i,N) {
		ll tmp=PS-P[i];
		if(i) tmp-=P[i-1];
		if(i+1<N) tmp-=P[i+1];
		ret+=P[i]*tmp%mo;
		
		if(i) ret+=hoge(i-1);
		if(i+1<N) ret+=hoge(i);
		
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

sum_i sum_j E(I(i,X)*I(j,X)) にするところがそもそも思い浮かばなかった。