kmjp's blog

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

AtCoder ABC #242 : Ex - Random Painting

なるほど…。
https://atcoder.jp/contests/abc242/tasks/abc242_h

問題

N個の白色のマスがある。
また、マスの区間[L[i],R[i]]がM通り与えられる。

1~Mが書かれたボールが1つずつあったとする。
ここからランダムに等確率でボールiを選び、マスにおいて対応する区間を黒く塗りつぶすことを考える。
同じボールは再度選ぶこともできるとき、全マス目が黒く塗りつぶされるまでのボール選択回数の期待値を求めよ。

解法

M個の区間中k個を選んだことがあり、かつまだ全マスが塗られていない場合、次に状態が更新される(新たなボールを選ぶ)までのボール選択回数の期待値はM/(M-k)である。
f(k) := M個の区間中k個を選んだ時、それでN個の全マスカバーできる組み合わせ

とすると、解は
 \displaystyle \sum_k \frac{Comb(M,k)-f(k)}{Comb(M,k)} \times \frac{M}{M-k}
となる。
f(x)は、区間をL[i]順にソートしておき、以下をO(N^3)かけてDPすればf(k)=g(N,N,k)として求められる。
g(i,r,k) := 先頭i個の区間のうちk個選んだ時、r番目までのマスが塗りつぶされているような区間の選び方

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

ll from[404][404];
ll to[404][404];

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(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<pair<int,int>> cand;
	FOR(i,M) {
		cin>>L[i]>>R[i];
		L[i]--;
		cand.push_back({L[i],R[i]});
	}
	from[0][0]=1;
	sort(ALL(cand));
	FORR2(l,r,cand) {
		ZERO(to);
		FOR(x,M) {
			for(y=l;y<=N;y++) {
				//not add
				(to[x][y]+=from[x][y])%=mo;
				//add
				(to[x+1][max(y,r)]+=from[x][y])%=mo;
			}
		}
		swap(from,to);
	}
	
	ll ret=0;
	FOR(i,M) {
		ll a=(comb(M,i)-from[i][N]+mo)*modpow(comb(M,i))%mo;
		ll b=M*modpow(M-i)%mo;
		(ret+=a*b)%=mo;
	}
	cout<<ret<<endl;
	
	
	
}

まとめ

うーむ、これ思いつかなかった…。