[Python] 動的計画法 TDPC D - Qiita

TDPC D 高校数学の確率問題（場合の数）として解くのは、6=2*3の処理が難しいので、情報数学の手法が適している。 部分構造最適性と部分問題重複性を有するので、動的計画法を検討する。 問題内のデータをそのまま実装するのは難しいので、単純化する必要がある。 積について考えるので、サイコロの目に存在する素因数 2,3,5 の指数のみを考えれば良い。 $10^{18}<2^{60}$ なので、指数として考える値はそれぞれ 60 以下でよいです。 動的計画法の設計は次の通り。 $dp[n][c_2][c_3][c_5]$の定義： $n$ 回振ったときに、出た目の積に含まれる素因数 2,3,5 の個数がそれぞれ$c_2,c_3,c_5$となる確率 dpの漸化式：