Problem p03178 (python)

Fixed submission:
string = input()
d = int(input())

nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = int(not bool(s))
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt
# print(mod(dfs() - 1))

for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = int(not bool(s))
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

print(mod(dp[0][0][1] - 1 + M))

Buggy submission (verdict: Runtime Error):
string = input()
nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)
d = int(input())

if length < 5:
    raise Exception()

Buggy submission (verdict: Runtime Error):
string = input()
nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)
d = int(input())

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d * 100)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = not bool(s)
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt

print(mod(dfs() - 1))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)

M = 10**9 + 7
K = int(input())
D = int(input())

dp = [[None] * 100 for _ in range(10**5 + 1)]
def f(k, i):
    if dp[i][k] is not None:
        return dp[i][k]

    if i == 0:
        r = (k % D) == 0
        dp[i][k] = r
        return r
    r = sum(f((k + x) % D, i - 1) for x in range(0, 10)) % M
    dp[i][k] = r
    return r

sk = str(K)
dig = len(sk)
answer = 0
s = sum(map(int, list(sk)))
for j in range(int(sk[-1]) + 1):
    if (s - j) % D == 0:
        answer += 1

if dig > 1:
    s -= int(sk[-1])
    for i in range(dig - 1, 1, -1):
        if sk[i - 1] == "0":
            continue
        for j in range(int(sk[i - 1])):
            answer += f(s - 1 - j, dig - i)
        s -= int(sk[i - 1])

    for k in range(1, int(sk[0])):
        answer += f(k, dig - 1)

    if dig > 1: # 先頭0固定
        for k in range(10):
            answer += f(k, dig - 2)


print((answer - 1) % M)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)

M = 10**9 + 7
K = int(input())
D = int(input())

dp = [[None] * 100 for _ in range(10**5 + 1)]
def f(k, i):
    if dp[i][k] is not None:
        return dp[i][k]

    if i == 0:
        r = (k % D) == 0
        dp[i][k] = r
        return r
    r = sum(f((k + x) % D, i - 1) for x in range(0, 10)) % M
    dp[i][k] = r
    return r

sk = str(K)
dig = len(sk)
answer = 0
s = sum(map(int, list(sk)))
for j in range(int(sk[-1]) + 1):
    if (s - j) % D == 0:
        answer += 1

if dig > 1:
    s -= int(sk[-1])
    for i in range(dig - 1, 1, -1):
        if sk[i - 1] == "0":
            continue
        for j in range(int(sk[i - 1])):
            answer += f(s - 1 - j, dig - i)
        s -= int(sk[i - 1])

    for k in range(1, int(sk[0])):
        answer += f(k, dig - 1)

    if dig > 1: # 先頭0固定
        for k in range(10):
            answer += f(k, dig - 2)


print((answer - 1) % M)

Buggy submission (verdict: Runtime Error):
M = 10**9 + 7
K = int(input())
D = int(input())

dp = [[None] * 100 for _ in range(10**5 + 1)]
def f(k, i):
    if dp[i][k] is not None:
        return dp[i][k]

    if i == 0:
        r = (k % D) == 0
        dp[i][k] = r
        return r
    r = sum(f((k + x) % D, i - 1) for x in range(0, 10)) % M
    dp[i][k] = r
    return r

sk = str(K)
dig = len(sk)
answer = 0
s = sum(map(int, list(sk)))
for j in range(int(sk[-1]) + 1):
    if (s - j) % D == 0:
        answer += 1

if dig > 1:
    s -= int(sk[-1])
    for i in range(dig - 1, 1, -1):
        if sk[i - 1] == "0":
            continue
        for j in range(int(sk[i - 1])):
            answer += f(s - 1 - j, dig - i)
        s -= int(sk[i - 1])

    for k in range(1, int(sk[0])):
        answer += f(k, dig - 1)

    if dig > 1: # 先頭0固定
        for k in range(10):
            answer += f(k, dig - 2)


print((answer - 1) % M)

Buggy submission (verdict: Runtime Error):
M = 10**9 + 7
K = int(input())
D = int(input())

dp = [[None] * 100 for _ in range(10**5 + 1)]
def f(k, i):
    if dp[i][k] is not None:
        return dp[i][k]

    if i == 0:
        r = (k % D) == 0
        dp[i][k] = r
        return r
    r = sum(f((k + x) % D, i - 1) for x in range(0, 10)) % M
    dp[i][k] = r
    return r

sk = str(K)
dig = len(sk)
answer = 0
s = sum(map(int, list(sk)))
for j in range(int(sk[-1]) + 1):
    if (s - j) % D == 0:
        answer += 1

if dig > 1:
    s -= int(sk[-1])
    for i in range(dig - 1, 1, -1):
        if sk[i - 1] == "0":
            continue
        for j in range(int(sk[i - 1])):
            answer += f(s - 1 - j, dig - i)
        s -= int(sk[i - 1])

    for k in range(1, int(sk[0])):
        answer += f(k, dig - 1)

    if dig > 1: # 先頭0固定
        for k in range(10):
            answer += f(k, dig - 2)


print((answer - 1) % M)