Problem p03178 (python)

Fixed submission:
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input().strip()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Buggy submission (verdict: Runtime Error):
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Buggy submission (verdict: Runtime Error):
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        # pre = [[0] * (d + 1) for _ in range(s + 1)]
        # for i in range(d):
        #     pre[1][i] = pre[1][i - 1] + dp[1][i]
        # for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            # cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            # for r in range(d):
            #     dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                # dp[l][r] = (dp[l - 1][r] + cur) % MOD
                # cur -= dp[l - 1][(r - 9) % d]
                # cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Buggy submission (verdict: Runtime Error):
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        # pre = [[0] * (d + 1) for _ in range(s + 1)]
        # for i in range(d):
        #     pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            # cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                # dp[l][r] = (dp[l - 1][r] + cur) % MOD
                # cur -= dp[l - 1][(r - 9) % d]
                # cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Buggy submission (verdict: Runtime Error):
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                # dp[l][r] = (dp[l - 1][r] + cur) % MOD
                # cur -= dp[l - 1][(r - 9) % d]
                # cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Buggy submission (verdict: Runtime Error):
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        # print(len(k))
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # print(l, r)
                # lo, hi = min((r - 1) % d, (r - 9) % d), max((r - 1) % d, (r - 9) % d)
                # assert((pre[l - 1][hi] - pre[l - 1][lo - 1]) == sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)))
                # dp[l][r] = (dp[l - 1][r] + (pre[l - 1][hi] - pre[l - 1][lo - 1])) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Buggy submission (verdict: Runtime Error):
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        # print(len(k))
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # print(l, r)
                # lo, hi = min((r - 1) % d, (r - 9) % d), max((r - 1) % d, (r - 9) % d)
                # assert((pre[l - 1][hi] - pre[l - 1][lo - 1]) == sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)))
                # dp[l][r] = (dp[l - 1][r] + (pre[l - 1][hi] - pre[l - 1][lo - 1])) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Buggy submission (verdict: Runtime Error):
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = int(input())
        d = int(input())

        s = len(str(k))
        dp = [[0] * d for _ in range(s)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1
        for l in range(2, s):
            for r in range(d):
                dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(str(k)[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in str(k))) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()