Codeforces #551 Div2 F. Serval and Bonus Problem

うーん、またこれ系か。
http://codeforces.com/contest/1153/problem/F

問題

区間[0,L]がある。
ここからN個の区間を選ぶ。区間の両端は整数位置でなくてもよく、その位置は等しい確率でランダムで選択される。

K個以上の区間で覆われる領域の長さの期待値を求めよ。

解法

区間を[0,1]として考え、最後にLを掛けても問題ない。
ある位置xに対し、その左側に左端・右側に右端が来る区間がK～N個あるケースを積分と数え上げて求めようとすると、かなり複雑な数値積分が登場して破たんする。

[0,1]から(2N+1)個の位置の並び順を考えよう。
具体的な位置は考えず、相対位置だけ考えて問題ない。これは各点が配置される位置が等確率なためである。

この(2N+1)個は、左端N個、右端N個、区間がK以上あるか判定する点1点、からなる。
「区間がK以上あるか判定する点1点」を配置する段階で、左端がすでに手前に登場しているのに右端が登場していないものがK個以上ある場合、解に加算されるされる。

よって以下をDPで求めればよい。最後に(2N+1)!で割ろう。
dp[配置済みの点の数][左端が来てまだ右端の来てない点の数][最後の1点が配置済みかどうか] := 組み合わせ数

int N,K,L;
ll mo=998244353;
ll dp[4020][2020][2];


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>>K>>L;
	
	dp[0][0][0]=1;
	FOR(x,2*N+1) {
		FOR(y,N+1) {
			// P
			if(y>=K) (dp[x+1][y][1]+=dp[x][y][0])%=mo;
			// open
			if(y<N) {
				(dp[x+1][y+1][0]+=dp[x][y][0])%=mo;
				(dp[x+1][y+1][1]+=dp[x][y][1])%=mo;
			}
			// close
			if(y) {
				(dp[x+1][y-1][0]+=y*dp[x][y][0])%=mo;
				(dp[x+1][y-1][1]+=y*dp[x][y][1])%=mo;
			}
			
		}
	}
	
	ll ret=dp[2*N+1][0][1];
	FOR(i,N) ret=ret*2%mo;
	for(i=1;i<=N;i++) ret=ret*i%mo;
	for(i=1;i<=2*N+1;i++) ret=ret*modpow(i)%mo;
	cout<<ret*L%mo<<endl;
}

まとめ

うまく式変形するとO(N)でも解ける様子。