Typical DP Contest：D - サイコロ
問題
解法
まず，D を素因数分解し，2, 3, 5 以外の素因数があった場合は，答えは 0 と決まる．
そうでないとき，「dp(i, tw, th, fi) := i 回サイコロを振り，素因数 2 が tw 回，素因数 3 が th 回，素因数 5 が fi 回出たとき，これからで出た目の積が D の倍数となる確率」と DP を立てる．各 DP で 1, 2, 3, 4, 5, 6 が出たときの DP の確率に 1 / 6 をかけたものが答えになる．
実装に当たっては，D の 2, 3, 5 の素因数の数よりも多く tw, th, fi を持っておく必要はないので，３つの素因数のそれぞれの数が D の３つの素因数のそれぞれの数と全て一致した段階でその DP では 1 を返せばよい．また，引数も min(tw, (D の素因数 2 の数)) などとすれば時間計算量・空間計算量ともに節約できる．O(Nα)．
解答
