Problem:


Score : 100 points

Problem Statement

Find the number of integers between 1 and K (inclusive) satisfying the following condition, modulo 10^9 + 7:

The sum of the digits in base ten is a multiple of D.

Constraints

All values in input are integers.

1 \leq K < 10^{10000}

1 \leq D \leq 100

Input

Input is given from Standard Input in the following format:

K
D

Output

Print the number of integers satisfying the condition, modulo 10^9 + 7.

Sample Input 1

30
4

Sample Output 1

6

Those six integers are: 4, 8, 13, 17, 22 and 26.

Sample Input 2

1000000009
1

Sample Output 2

2

Be sure to print the number modulo 10^9 + 7.

Sample Input 3

98765432109876543210
58

Sample Output 3

635270834



Sample input:
30
4


Sample output:
6

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10070)
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
MOD = 10**9 + 7

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        sum += dp[sz-1][(r-i)%d]
        if sum >= MOD:
            sum -= MOD
    return sum

k = input()
d = inn()
e = len(k)
dp = [ [0 for i in range(d)] for j in range(e) ]
for i in range(10):
    dp[1][i%d] += 1
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
        if dp[i][j] >= MOD:
            dp[i][j] -= MOD
print((f(k,0)-1)%MOD)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10070)
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
MOD = 10**9 + 7

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        sum += dp[sz-1][(r-i)%d]
        if sum >= MOD:
            sum -= MOD
    return sum

k = input()
d = inn()
e = len(k)
dp = [ [0 for i in range(d)] for j in range(e) ]
for i in range(10):
    dp[1][i%d] += 1
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
        if dp[i][j] >= MOD:
            dp[i][j] -= MOD
print(f(k,0)-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10030)
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
MOD = 10**9 + 7

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        sum += dp[sz-1][(r-i)%d]
        if sum >= MOD:
            sum -= MOD
    return sum

k = input()
d = inn()
e = len(k)
dp = [ [0 for i in range(d)] for j in range(e) ]
for i in range(10):
    dp[1][i%d] += 1
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
        if dp[i][j] >= MOD:
            dp[i][j] -= MOD
print(f(k,0)-1)

Submission status: Runtime Error

Solution code:
import sys,heapq
sys.setrecursionlimit(10030)
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
MOD = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        ddprint("sum {} sz {} r {} i {} d {} dp {}".format(sum, sz, r, i, d, dp[sz-1][(r-i)%d]))
        sum = (sum + dp[sz-1][(r-i)%d]) % MOD
    ddprint("f s={} r={} rtns {}".format(s,r,sum))
    return sum

k = input()
d = inn()
e = len(k)
ddprint("k {} d {} e {}".format(k,d,e))
dp = [ [0 for i in range(d)] for j in range(e) ]
for i in range(10):
    dp[1][i%d] += 1
ddprint(dp[1])
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
  ddprint(dp[i])
print(f(k,0)-1)

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
N_str = input()
D = int(input())

max_k = len(N_str)
dp = [[[-1]*D for i in range(2)] for j in range(max_k) ]

def rec(k=0, tight=True, mod_sum=0):
    if k == max_k:
        return int(mod_sum==0)
    if dp[k][tight][mod_sum] >= 0:
        return dp[k][tight][mod_sum]
    top = 9 if not tight else int(N_str[k])
    res = 0
    for i in range(top+1):
        res += rec(k+1, tight and i==top, (mod_sum+i) % D)
        res %= mod
    dp[k][tight][mod_sum] = res
    return res

print(rec()-1)

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
N_str = input()
D = int(input())

max_k = len(N_str)
dp = [[[-1]*D for i in range(2)] for j in range(max_k) ]

def rec(k=0, tight=True, mod_sum=0):
    if k == max_k:
        return int(mod_sum==0)
    if dp[k][tight][mod_sum] >= 0:
        return dp[k][tight][mod_sum]
	top = 9 if not tight else int(N_str[k])
    res = 0
    for i in range(top+1):
        res += rec(k+1, tight and i==top, (mod_sum+i) % D)
        res %= mod
    dp[k][tight][mod_sum] = res
    return res

print(rec()-1)

Submission status: Runtime Error

Solution code:
a = 10002
b = 102
c = 3

dp = [[[-1 for z in range(c)] for y in range(b)] for x in range(a)]

num = []

MOD = 1000000007

def solve(index, summ, flag, d, val):
	if index == len(num):
		return summ % d == 0

	if dp[index][summ][flag] != -1:
		return dp[index][summ][flag]

	limit = 0
	result = 0
	if flag == 0:
		limit = num[index]
	else:
		limit = 9

	for digit in range(0,limit+1):
		nflag = flag
		nsum = (summ + digit)%d
		if flag == 0 and digit < limit:
			nflag = 1
		nval = val*10 + digit
		result = result + solve(index+1, nsum, nflag, d, nval)
		result = result % MOD

	dp[index][summ][flag] = result
	return result

def initialize(k):
	for c in k:
		num.append(int(c))

k = input()
d = int(input())
initialize(k)
print(solve(0,0,0,d,0) - 1)

Submission status: Runtime Error

Solution code:
K = input()
D = int(input())
L = len(K)
MOD = 10**9+7
dp = [[[0]*D for j in range(2)] for i in range(L+1)] #dp[i][less][modD]
dp[0][0][0] = 1
for i,c in enumerate(K):
    for less in range(2):
        lim = 9 if less else int(c)
        for d in range(lim+1):
            dp[i+1][less or d < lim][(r+d)%D] += dp[i][less][r]
            dp[i+1][less or d < lim][(r+d)%D] %= MOD

print((dp[-1][0][0] + dp[-1][1][0] - 1) % MOD)

Submission status: Runtime Error

Solution code:
k = input()
d = int(input())
n = len(k)
m = 1000000007
dp = [[-1 for i in range(100)] for j in range(10000)]

def f(x, s, b):
    if x == n:
        if s%d == 0: return 1
        return 0
    u = 9
    r = 0
    if b == True: u = int(k[x])
    elif dp[x][s] != -1: return dp[x][s]
    for i in range(u+1):
        r = (r + f(x+1, (s+i)%d, b and i == u))%m
    if b == False: dp[x][s] = r
    return r

ans = (f(0, 0, True) - 1 + m)%m
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
K = input()
N = len(K)
D = int(input())
S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[d+v-D][1] += w0
        T[d+c-D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[d+v-D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)