kmjp's blog

競技プログラミング参加記です

Codeforces ECR #081 : F. Good Contest

自画自賛…?
http://codeforces.com/contest/1295/problem/F

問題

N要素の整数列Aを構築することを考える。
整数列L,Rが与えられており、A[i]は[L[i],R[i]]の範囲の整数を等しい確率で選択するとする。
Aが単調減少になる確率を求めよ。

解法

まず区間を座標圧縮しよう。
次にDPしていくのだが、Aの各要素は直前と同じ区間かそれより小さな値の区間になければならない。
後者は累積和で容易に求められるが、複数の連続要素が同一区間に属する場合は別途考慮が必要である。
とはいえこれは単なる重複組み合わせの数え上げに持ち込める。

DPの際は、Aの各添え字と各区間に対し、同じ区間に属する要素がいくつ連続するかを総当たりするとよい。
全体で座標圧縮後の区間数がO(N^2)、処理対象の添え字がN個、連続数をO(N)とすると全体でO(N^4)の時間で解ける。

int N;
int L[51],R[51];
const ll mo=998244353;

ll dp[60][120];

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 comb(int P_,int Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--;
	
	return p*modpow(q,mo-2)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> V;
	cin>>N;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		R[i]++;
		V.push_back(L[i]);
		V.push_back(R[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	
	dp[0][V.size()-1]=1;
	FOR(x,N) {
		FOR(y,V.size()-1) {
			ll sum=0;
			for(i=y+1;i<V.size();i++) sum+=dp[x][i];
			sum%=mo;
			if(sum==0) continue;
			for(i=x;i<N;i++) {
				if(L[i]<=V[y]&&V[y]<R[i]) {
					(sum*=(V[y+1]-V[y])*modpow(R[i]-L[i])%mo)%=mo;
					(dp[i+1][y]+=sum*comb(V[y+1]-V[y]-1+i+1-x,i+1-x)%mo*modpow(modpow(V[y+1]-V[y],i+1-x)))%=mo;
				}
				else {
					break;
				}
			}
		}
	}
	ll ret=0;
	FOR(y,V.size()) ret+=dp[N][y];
	cout<<ret%mo<<endl;
	
}

まとめ

ECRの最終問にしては楽。