TopCoder SRM 391 Div1 Medium KeysInBoxes
嫌がらせかよこれ
問題
N個の箱と、それぞれの箱の鍵がある。
それぞれの箱の中に、鍵がランダムに一つ入っている。
鍵の入れ方は、全ての入れ方の中から等しい確率で一つが選ばれる。
爆弾をM個持っていて、爆弾を一つ使うと、箱を一つ壊して開けることができる。
全ての箱の鍵を手に入れられる確率を、a/b(ただしa,bは互いに素な整数)
の形で求めよ。
制約条件
N,M≦20
方針
dp[pos][tmp][bomb]を、
pos個の箱を既に開け終えて、tmpの箱を今開けている最中で、bomb個の爆弾を持っている時に全部の箱を開けられる確率とする。
tmpが0の場合、爆弾を一つ使う。
そうでないとき、今の箱に入っている鍵は、
- tmpの箱のどれかの鍵
- tmpじゃない箱の鍵
である場合があり、前者の場合tmpが0になって、
後者の場合posが1増えて、tmpも1増える。
ソースコード
BigNumはspaghetti sourceの多倍長クラス。
BigNum gcd(BigNum x,BigNum y){ return y==ZERO?x:gcd(y,x%y); } struct F{ BigNum a,b; F(){a=ZERO,b=ONE;} void normal(){ BigNum d=gcd(a,b); a=a/d; b=b/d; } bool operator==(F y){ return a==y.a&&b==y.b; } F(BigNum a,BigNum b):a(a),b(b){ normal(); } F(ll x,ll y):a(1,x),b(1,y){ normal(); } string str(){ stringstream ss; ss<<a<<"/"<<b; return ss.str(); } F operator+(F y){ F c(y.b*a+b*y.a,b*y.b); c.normal(); return c; } F operator*(F y){ BigNum d=gcd(a,y.b); a=a/d; y.b=y.b/d; d=gcd(b,y.a); b=b/d; y.a=y.a/d; F c(a*y.a,b*y.b); c.normal(); return c; } }; F dp[21][21][21]; F rec(int n,int tmp,int m){ if(m<0)return F(0,1); if(!(dp[n][tmp][m]==F(2,1)))return dp[n][tmp][m]; F &res=dp[n][tmp][m]; if(n==0)return res=F(1,1); if(m==0)return res=F(n,n+1)*rec(n-1,tmp+1,m); if(tmp>0){ res=F(n,n+1)*rec(n-1,tmp+1,m)+F(1,n+1)*rec(n,0,m); return res; } return res=rec(n-1,1,m-1); } class KeysInBoxes { public: string getAllKeys(int N, int M) { rep(i,21)rep(j,21)rep(k,21){ dp[i][j][k]=F(2,1); } return rec(N,0,M).str(); } };