SRM435 Div2 Hard

1000

dp[何日目][何匹にマークした]

最初は、2^20 * 2^20 * 5 が思い浮かんで絶望した。

class BirdsCounting {
public:
  double computeProbability(int birds, int caught, int days, int marked)
  {
    const int B = 20 + 2;
    const int D = 5 + 2;

    double nCk[B][B];
    fill(&nCk[0][0], &nCk[B][0], 0);
    nCk[0][0] = 1;

    for (int n = 1; n < B; ++n) {
      nCk[n][0] = 1;
      for (int k = 1; k < B; ++k) {
        nCk[n][k] = nCk[n - 1][k - 1] + nCk[n - 1][k];
      }
    }

    double dp[D][B];
    fill(&dp[0][0], &dp[D][0], 0);
    dp[0][0] = 1;

    for (int d = 0; d < days; ++d) {
      for (int b = 0; b <= birds; ++b) {
        for (int i = 0; i <= caught; ++i) {
          if (b + i <= marked) ; else continue;
          if (0 <= caught - i) ; else continue;
          double p = nCk[birds - b][i] * nCk[b][caught - i] / nCk[birds][caught];
          dp[d + 1][b + i] += dp[d][b] * p;
        }
      }
    }

    return dp[days][marked];
  }
};