Codeforces #1012 : Div1 C2. Key of Like (Hard Version)

問題文が長い…。
https://codeforces.com/contest/2089/problem/C2

問題

L個の錠と、(L+K)個の鍵がある。L組の鍵と錠が互いに対応づく。
これらを、N人で順に開けたい。
各人は、錠と鍵を選び、開けるか試みる。開けたらその人はその組を得る。開けられなければ、錠と鍵は元に戻す。
いずれにしても、次の人に順番が移る。
各人は、他人も含めどの錠と鍵の組み合わせが試されたかをすべて把握しており、自身の順番では最も成功率が高い組み合わせを試す。
ただし、同着が複数あるならどれかを等確率でランダムに選ぶ。

N,L,Kが与えられたとき、各人が得られる明けられた錠と鍵の組み合わせの数の期待値を求めよ。

解法

f(n,l) := 残った未着手の鍵がl個あるとき、次の手番からn番目の人が得られる錠と鍵の期待
とし、f(n,l)からf(n',l+1)を更新していこう。最終的にf(0,L),f(1,L),f(2,L),....が解となる。

最初、または直前に他人が錠と鍵の組み合わせを当てたとき、次の手番の人は、錠と鍵の組み合わせをランダムに試す。
それが失敗の場合、2番目の人は、錠を変える場合と鍵を変える場合がある。3番目以降の人は、2番目の人をマネする。
その結果、2番目以降の人の成功率はみな等しいので、累積和の要領でf(n,l)の値をf(n',l+1)に足しこんでいこう。

int T,N,L,K;
const 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 from[27][101];
ll to[27][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ZERO(from);
		cin>>N>>L>>K;
		for(l=1;l<=L;l++) {
			ZERO(to);
			FOR(k,K+1) {
				// 初手成功確率
				int p=modpow(l+k);
				(to[k][0]+=p)%=mo;
				FOR(x,N) (to[k][(x+1)%N]+=p*from[k][x])%=mo;
				int kp=(1LL+mo-p)*(l+k-1)%mo*modpow(2*l+k-2)%mo; //鍵交換
				int lp=(1LL+mo-p)*(l-1)%mo*modpow(2*l+k-2)%mo; //錠交換
				
				ll dp2[202]={};
				if(lp) {
					int p=lp*modpow(l+k-1)%mo;
					//いずれ当たる
					dp2[0]+=1LL*p*((l-1)/N)%mo;
					dp2[N]-=1LL*p*((l-1)/N)%mo;
					dp2[1]+=p;
					dp2[1+(l-1)%N]+=mo-p;
					
					FOR(x,N) {
						y=(x+2)%N;
						dp2[0]+=1LL*p*((l-1)/N)%mo*from[k][x]%mo;
						dp2[N]+=mo-1LL*p*((l-1)/N)%mo*from[k][x]%mo;
						dp2[y]+=p*from[k][x]%mo;
						dp2[y+(l-1)%N]+=mo-p*from[k][x]%mo;
						
					}
					if(k) {
						ll fail=1LL*p*k%mo;
						FOR(x,N) (to[k][(x+l)%N]+=fail*to[k-1][x])%=mo;
					}
				}
				if(kp) {
					//いずれ当たる
					int p=kp*modpow(l+k-1)%mo;
					dp2[0]+=1LL*p*((l+k-1)/N)%mo;
					dp2[N]-=1LL*p*((l+k-1)/N)%mo;
					dp2[1]+=p;
					dp2[1+(l+k-1)%N]+=mo-p;
					
					FOR(x,N) {
						y=(x+2)%N;
						dp2[0]+=1LL*p*((l+k-1)/N)%mo*from[k][x]%mo;
						dp2[N]+=mo-1LL*p*((l+k-1)/N)%mo*from[k][x]%mo;
						dp2[y]+=p*from[k][x]%mo;
						dp2[y+(l+k-1)%N]+=mo-p*from[k][x]%mo;
						
					}
				}
				FOR(x,2*N) {
					(to[k][x%N]+=dp2[x])%=mo;
					(dp2[x+1]+=dp2[x])%=mo;
				}
			}
			swap(from,to);
			/*
			FOR(k,K+1) {
				cout<<l<<" "<<k<<" ";
				FOR(x,N) cout<<from[k][x]<<" ";
				cout<<endl;
			}
			*/
		}
		
		FOR(i,N) cout<<from[K][i]<<" ";
		cout<<endl;
		
	}
}

まとめ

2番目以降の人の最適手を、ぱっと思いつけなかった。