Since it is difficult to process 6 = 2 * 3 to solve as a probability problem (number of cases) in high school mathematics, the method of information mathematics is suitable. Since it has partial structure optimality and subproblem duplication, dynamic programming is considered.
It is difficult to implement the data in the problem as it is, so it needs to be simplified.
Since we are thinking about the product, we only need to consider the exponents of the prime factors 2,3,5 that exist in the dice.
Since $ 10 ^ {18} <2 ^ {60} $, each value considered as an exponent can be 60 or less.
The design of dynamic programming is as follows.
Definition of $ dp [n] [c_2] [c_3] [c_5] $: Probability that the number of prime factors 2,3,5 included in the product of the rolled numbers will be $ c_2, c_3, c_5 $, respectively, when shaken $ n $ times.
dp recurrence formula:
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 initial condition:
$ dp [0] [0] [0] [0] = 1 $ (When shaken 0 times, the product of the eyes is 1, so the prime factors do not include any prime numbers)
What you want:
When $ 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]
Implementation is done by the DP distributed by the bottom-up method.
Sample code
n, d = map(int, input().split())
#Factoring the dice roll into 2, 3,Only 5 appear
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,No if there is anything other than 5
if d != 1:
print(0)
exit()
#dp initialization
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
#Dice roll 1~Prime factorization of 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] :=Roll the dice i times, 2^c2 * 3^c3 * 5^Probability of becoming c5
for i in range(n):
# c2,c3,c About 5 and 6 eyes i+Update 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])
Recommended Posts