問題概要

問題文はこちらを参照してください。

解法

まずは、1～6の積が$D$の倍数にならないといけないので、$D$を素因数分解したときに、2,3,5以外の要素が含まれていると確率は0になるということがわかります。したがって、$D$の素因数分解が必要になります。素因数分解は単純に2,3,5それぞれで何回割り切れるのかを計算して、$D=2^I\cdot 3^J\cdot 5^K$と表されるとします。

このように考えると、サイコロを$N$回振った時に出た目の積が、それぞれ$2^I\cdot 3^J\cdot 5^K$よりも多い要素でできている確率と考えられます。$n$回目の試行で$2^i\cdot 3^j\cdot 5^k$だった場合、例えば$n+1$回目の試行で2の目が出る$\frac{1}{6}$の確率分、$2^{i+1}\cdot 3^j\cdot 5^k$になる確率が増えます。このようにすべての目が出る確率を計算していきます。

漸化式の定義： \begin{eqnarray} dp[n+1][i][j][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (1の目が出たとき）\\ dp[n+1][i+1][j][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (2の目が出たとき）\\ dp[n+1][i][j+1][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (3の目が出たとき）\\ dp[n+1][i+2][j][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (4の目が出たとき）\\ dp[n+1][i][j][k+1] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (5の目が出たとき）\\ dp[n+1][i+1][j+1][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (6の目が出たとき） \end{eqnarray}

$dp[n][i][j][k]$：サイコロを$n$回振った時、出た目の積が$2^i\cdot 3^j\cdot 5^k$と表される確率
$(0\le n \le N,\ 0\le i \le I,\ 0\le j \le J,\ 0\le k \le K)$

初期値：$dp[0][0][0][0]=1$

求める解：$dp[n][I][J][K]$

ただし、上記漸化式左辺の$i,j,k$の部分は、$i+2=\min\{i+2,I\}$などと考え、$2^{I+2}$などになる確率は$dp[n][I][j][k]$に加えるようにして、$i=I$の時は$2^i$ちょうどではなく、$2^I$以上と表される確率とします。

考察

確率の問題は配るＤＰで足していくといいことが多い気がします。特に今回は$2^I$以上のものをまとめたいので、そちらのほうがわかりやすいと思います。