問題文
解法
倍数判定なので、まずはDを素因数分解する。このうち、サイコロの出目は1〜6のみなので、この範囲の素因数のみを考えれば良い。つまり、Dを以下のように分解して考える。
$$D = 2^a \cdot 3^b \cdot 5^c \cdot R$$
あとはDPをする。今回の場合は、出目を列挙する必要はなく、今までに降った中で条件を満たす確率さえわかればよい。そのため、以下のように考える。
N回サイコロを降った時、出目の積の因数のうち、2がa回以上、3がb回以上、5がc回以上含まれている場合、出目の積がDの倍数である確率
遷移式は以下の通り。
\begin{eqnarray} dp[0][0][0][0] &=& & &1 \\ dp[N][a][b][c] &=& & &dp[N-1][a][b][c] \\ && &+&dp[N-1][a-1][b][c] \cdot \frac{1}{6} \\ && &+&dp[N-1][a][b-1][c] \cdot \frac{1}{6} \\ && &+&dp[N-1][a-2][b][c] \cdot \frac{1}{6} \\ && &+&dp[N-1][a][b][c-1] \cdot \frac{1}{6} \\ && &+&dp[N-1][a-1][b-1][c] \cdot \frac{1}{6} \\ \end{eqnarray}
左辺と右辺に注目するとサイコロを振った回数Nの状態は保持しておく必要がないことがわかる。そのため、最終的な遷移式は以下の通り。
\begin{eqnarray} dp[0][0][0] &=& & &1 \\ dp[a][b][c] &=& & &dp[a][b][c] \\ && &+&dp[a-1][b][c] \cdot \frac{1}{6} \\ && &+&dp[a][b-1][c] \cdot \frac{1}{6} \\ && &+&dp[a-2][b][c] \cdot \frac{1}{6} \\ && &+&dp[a][b][c-1] \cdot \frac{1}{6} \\ && &+&dp[a-1][b-1][c] \cdot \frac{1}{6} \\ \end{eqnarray}
