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();
  }
};