5箇所を選ぶパターン数を数える。
DP[何列目まで決めた][残り何箇所][勝利状態かどうか] = パターン数
dp[N][0][true] / (dp[N][0][true] + dp[N][0][false])
で確率が出る。
class LotteryPyaterochka { public: double chanceToWin(int N) { const int M = 5; int p[M]; fill(p, p + M, 0); for (int bit = 0; bit < (1 << M); ++bit) { int cnt = 0; for (int i = 0; i < M; ++i) { if (bit & (1 << i)) ++cnt; } ++p[cnt]; } const int C = 5 + 1; double dp[N + 1][C][2]; fill(&dp[0][0][0], &dp[N][C - 1][2 - 1] + 1, 0); dp[0][5][0] = 1; for (int i = 0; i < N; ++i) { for (int j = 0; j < C; ++j) { for (int k = 0; k < 2; ++k) { for (int l = 0; l <= j; ++l) { dp[i + 1][j - l][k || (3 <= l)] += dp[i][j][k] * p[l]; } } } } return dp[N][0][true] / (dp[N][0][true] + dp[N][0][false]); } }