高校数学の確率問題(場合の数)として解くのは、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の漸化式:
dp[n][nc_2][nc_3][nc_5]=\sum_{i=0}^{n-1}\sum_{c_2\ge nc_2, c_3 \ge nc_3, c_5 \ge nc_5}dp[i][c_2][c_3][c_5]
dp初期条件:
$dp[0][0][0][0]=1$(0 回振ったとき、目の積を 1 とするので、素因数にいかなる素数も含まれない)
$dp[0][][][]=0$
求めるもの:
$D=2^a 3^b 5^c$のとき
\sum_{p_2\ge a, p_3 \ge b, p_5 \ge c}dp[N][p_2][p_3][p_5]
実装は、ボトムアップ方式の配るDPで行う。
サンプルコード
n, d = map(int, input().split())
# サイコロの目を素因数分解すると、2, 3, 5しか現れない
count2 = 0
count3 = 0
count5 = 0
while d % 2 == 0:
d //= 2
count2 += 1
while d % 3 == 0:
d //= 3
count3 += 1
while d % 5 == 0:
d //= 5
count5 += 1
# 2, 3, 5以外があったらだめ
if d != 1:
print(0)
exit()
# dp初期化
dp = [[[[0] * (count5 + 1) for i in range(count3 + 1)] for j in range(count2 + 1)] for k in range(n + 1)]
dp[0][0][0][0] = 1
# サイコロの目1~6を素因数分解
d2 = [0, 1, 0, 2, 0, 1]
d3 = [0, 0, 1, 0, 0, 1]
d5 = [0, 0, 0, 0, 1, 0]
# dp[i][c2][c3][c5] := サイコロを i 回振って、2^c2 * 3^c3 * 5^c5 になる確率
for i in range(n):
# c2,c3,c5および6つの目についてi+1のdpを更新
for c2 in range(count2 + 1):
for c3 in range(count3 + 1):
for c5 in range(count5 + 1):
for j in range(6):
nc2 = min(count2, c2 + d2[j])
nc3 = min(count3, c3 + d3[j])
nc5 = min(count5, c5 + d5[j])
dp[i + 1][nc2][nc3][nc5] += dp[i][c2][c3][c5] / 6
print(dp[n][count2][count3][count5])