なるほど…。
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個の全マスカバーできる組み合わせ
とすると、解は
となる。
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; }
まとめ
うーむ、これ思いつかなかった…。