Typical DP Contest D - サイコロ

問題
提出コード
復習問題だったのですが、見事MLEを吐きました。

解法

を素因数分解したときに登場する2の個数、とします(3,5も同様です)。
基本的な方針としては、
回サイコロを振ったときに、2が回、3が回、5が回登場するような確率
とします。4は2が2回分、6は2と3が1回ずつ分として計算します。
初期状態は、です。
回目に、1~6のどれを出すか、で遷移を行っていきます。
1から順番に、それぞれ以下のようになります。

答えは、を素因数分解したときに2,3,5以外の素因数が含まれていたら0、そうでなければとなるを選んだ時のの総和です。 ただし、このままだと途中でMLEやらなんやらを吐きACすることができません(少なくとも自分はそうでした)。そこで、回目でがそれぞれにたどり着いた時点で、それ以降は1~6のどの目がでても問題の条件を満たす、ということに着目すると、以下のようにDPを組み替えることができます。

このように組み替えることで、メモリを抑えつつ、また、答えはを見るだけでわかるようになります。