SRM488 Div1 Easy

250
E(n, m) = p0 * E(n, m) + p1 * E(n + 1, m - 1) + p2 * E(n + 2, m - 2) みないになるから式を変形。

カッコを付け忘れた、+と*を間違えた、再帰はしてたけどメモ化してなかった。
散々だった。

const int N = (47 + 1) * 2;
const int M = 47 + 1;

double t[N][M];

double e(int n, int m)
{
  if (m <= 0) return 0;
  if (t[n][m] != -1) return t[n][m];

  double w = (n + m) * (n + m - 1) / 2.0;
  double p0 = (double)(n * (n - 1)) / 2.0 / w;
  double p1 = (double)(n * m) / w;
  double p2 = (double)(m * (m - 1)) / 2.0 / w;

  return t[n][m] = (1.0 + p1 * e(n + 1, m - 1) + p2 * e(n + 2, m - 2)) / (1.0 - p0);
}

class TheBoredomDivOne {
public:
  double find(int n, int m)
  {
    fill(&t[0][0], &t[N - 1][M], -1);    
    return e(n, m);
  }

};