Submission #18352622

---

Source Code Expand

#!/usr/bin/env python3
# from typing import *


dp = {}
dp[0, 0, 0, 0] = 1

def dfs(n, k2, k3, k5):
    if (n, k2, k3, k5) in dp:
        return dp[n, k2, k3, k5]
    
    dfs(n-1, k2, k3, k5) \
        + dfs(n-1, k2-1, k3, k5) \
        + dfs(n-1, k2, k3-1, k5) \
        + dfs(n-1, k2-2, k3, k5) \
        + dfs(n-1, k2, k3, k5-1) \
        + dfs(n-1, k2-1, k3-1, k5)
    


# def solve(a: int, b: int) -> float:
def solve(N, D):
    k2 = 0
    k3 = 0
    k5 = 0
    while D % 2 == 0:
        D = D // 2
        k2+=1
    while D % 3 == 0:
        D = D // 3
        k3+=1
    while D % 5 == 0:
        D = D // 5
        k5+=1
    
    if D != 1:
        return 0

    dp = [[[[0 for _ in range(k5+1)] for _ in range(k3+1)] for _ in range(k2+1)] for _ in range(N+1)]

    dp[0][0][0][0] = 1
    for n in range(N):
        for c2 in range(k2+1):
            for c3 in range(k3+1):
                for c5 in range(k5+1):

                    p = dp[n][c2][c3][c5]
                    add = p / 6

                    dp[n+1][c2][c3][c5] += add
                    dp[n+1][min(c2+1, k2)][c3][c5] += add
                    dp[n+1][c2][min(c3+1, k3)][c5] += add
                    dp[n+1][min(c2+2, k2)][c3][c5] += add
                    dp[n+1][c2][c3][min(c5+1, k5)] += add
                    dp[n+1][min(c2+1, k2)][min(c3+1, k3)][c5] += add

    return dp[N][k2][k3][k5]

# generated by online-judge-template-generator v4.7.1 (https://github.com/online-judge-tools/template-generator)
def main():
    a, b = map(int, input().split())
    a1 = solve(a, b)
    print(a1)

if __name__ == '__main__':
    main()

Submission Info

Judge Result