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: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


sys.setrecursionlimit(10 ** 6)


@lru_cache(None)
def rec(n, curr, rem):
    if not n:return 1 if curr % rem == 0 else 0
    ans = 0
    for j in range(10):
        ans = (ans + rec(n - 1, (curr + j) % rem, rem)) % mod
    return ans


k = st()
d = val()
n = len(k)

curr = ans = 0


for i in range(n):
    for j in range(int(k[i])):
        ans = (ans + rec(n - i - 1, (curr + j) % d, d)) % mod


    curr = (curr + int(k[i])) % d

if curr % d == 0:ans += 1
ans -= 1

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def main():
    K = input().replace("\n", "")
    D = int(input())
    
    mod = pow(10, 9)+7
    n = len(K)
    dp = [[0]*D for _ in range(n+1)]
    
    dp[0][0] = 1
    sub = 0
    
    if D == 1:
        ans = 0
        for i in range(n):
            ans = (ans*10+int(K[i]))%mod
        print(ans)
        sys.exit()


    for i in range(n):
        if i != 0:
            for j in range(10):
                for k in range(D):
                    dp[i+1][(k+j)%D] += dp[i][k]
                    dp[i+1][(k+j)%D] %= mod
            for j in range(1, 10):
                dp[i+1][j%D] += 1
                dp[i+1][j%D] %= mod
        
        
        for j in range(int(K[i])):
            if i == 0 and j == 0:
                continue
            dp[i+1][(j+sub)%D] += 1
            dp[i+1][(j+sub)%D] %= mod
        sub = (sub+int(K[i]))%D
    
    sub = 0
    for i in range(n):
        sub = (sub+int(K[i]))%D
    if sub == 0:
        dp[n][0] += 1
        dp[n][0] %= mod
        
    
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

K = input()
D = int(input())

n = len(K)

dp = [[[0 for k in range(D)] for j in range(2)] for i in range(n+1)]
dp[0][0][0] = 1

for i in range(1,n+1):
    for k in range(D):
        for j in range(10):
            dp[i][1][k] += dp[i-1][1][(k-j) % D]
        for j in range(int(K[i-1])):
            dp[i][1][k] += dp[i-1][0][(k-j) % D]
        dp[i][0][k] += dp[i-1][0][(k-int(K[i-1])) % D]

print((dp[n][1][0] + dp[n][0][0] -1) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

# dp[i][smaller][d] : i桁目で、K未満で、そこまでの総和をDで割った余り = 個数

K = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
keta = len(K)

dp = [[[0] * D for i in range(2)] for j in range(keta)]

x0 = int(K[0])
dp[0][0][x0 % D] = 1
bef = x0 % D # 未満じゃないときに直前に値が入っているmodを記録しておく
for i in range(x0):
  dp[0][1][i % D] += 1
  
for i in range(1, keta):
  x = int(K[i])
  
  # 未満じゃない -> 未満じゃない
  dp[i][0][(bef + x) % D] = 1
  
  # 未満じゃない -> 未満
  # 0~x-1の値を取り得る
  for j in range(x):
    dp[i][1][(bef + j) % D] += dp[i - 1][0][bef]
  
  for j in range(D):
    dp[i][1][j] %= DIV
  
  bef = (bef + x) % D # 未満じゃないときに値が入っているmodを記録
  
  # 未満 -> 未満
  for j in range(D):
    for k in range(10): # 0~9のすべてを取れる
      dp[i][1][(k + j) % D] += dp[i - 1][1][j]
      
  for j in range(D):
    dp[i][1][j] %= DIV

print((dp[-1][0][0] + dp[-1][1][0] - 1) % DIV) # 0を数えないので引く

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from numba import jit


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

@jit
def digit_dp(n, f):
    l = len(str(n))
    dp = [[[0] * f for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        max_d = int(str(n)[i])
        for j in range(2):
            for k in range(f):
                for d in range(10 if j else max_d + 1):
                    dp[i + 1][j or (d < max_d)][(k + d) % f] += dp[i][j][k]
                    dp[i + 1][j or (d < max_d)][(k + d) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = I()
d = I()
print(digit_dp(k, d) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def digit_dp(n, f):
    l = len(str(n))
    dp = [[[0] * f for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        max_d = int(str(n)[i])
        for j in range(2):
            for k in range(f):
                for d in range(10 if j else max_d + 1):
                    dp[i + 1][j or (d < max_d)][(k + d) % f] += dp[i][j][k]
                    dp[i + 1][j or (d < max_d)][(k + d) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = I()
d = I()
print(digit_dp(k, d) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def digit_dp(n, f):
    dp = [[[0] * f for _ in range(2)] for _ in range(10002)]
    dp[0][0][0] = 1
    l = len(str(n))
    for i in range(l):
        max_d = int(str(n)[i])
        for j in range(2):
            for k in range(f):
                for d in range(10 if j else max_d + 1):
                    dp[i + 1][j or (d < max_d)][(k + d) % f] += dp[i][j][k]
                    dp[i + 1][j or (d < max_d)][(k + d) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = I()
d = I()
print(digit_dp(k, d) % mod)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

    strN = input().rstrip()
    D = int(input())

    maxD = len(strN)

    dp = [[[0]*(D) for j in range(2)] for i in range(maxD+1)]
    dp[0][0][0] = 1
    for d, Nd in enumerate(strN):
        Nd = int(Nd)
        for isLtN in range(2):
            for modD in range(D):
                dp[d][isLtN][modD] %= MOD
                for x in range(10):
                    if not isLtN and x > Nd: continue
                    isLtN2 = isLtN or x < Nd
                    modD2 = (modD+x) % D
                    dp[d+1][isLtN2][modD2] += dp[d][isLtN][modD]

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


solve()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

K = map(int, iter(input()))
D = int(input())

s = 0
dp = [0] * D
for k in K:
    ndp = [0] * D
    for d in range(10):
        for i, dpi in enumerate(dp):
            ndp[(i + d) % D] += dpi

    for d in range(k):
        ndp[(s + d) % D] += 1

    s = (s + k) % D
    dp = [x % mod for x in ndp]

print((dp[0] - (s != 0)) % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

K = map(int, list(input()))
D = int(input())

s = 0
dp = [0] * D
for k in K:
    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] = (T[(i + x) % D] + dpi) % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

K = input()
D = int(input())

s = 0
dp = [0] * D
for k in K:
    k = int(k)

    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] += dpi
            T[(i + x) % D] % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10 ** 9 + 7

    K = list(map(int, list(input())))
    D = int(input())

    s = 0
    dp = [0] * D
    for k in K:
        T = [0] * D
        for i, dpi in enumerate(dp):
            for x in range(10):
                T[(i + x) % D] += dpi
                T[(i + x) % D] % mod
        for x in range(k):
            T[(s + x) % D] += 1

        s = (s + k) % D
        dp = T

    print((dp[0] + (-1 if s != 0 else 0)) % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10 ** 9 + 7

    K = map(int, list(input()))
    D = int(input())

    s = 0
    dp = [0] * D
    for k in K:
        T = [0] * D
        for i, dpi in enumerate(dp):
            for x in range(10):
                T[(i + x) % D] += dpi
                T[(i + x) % D] % mod
        for x in range(k):
            T[(s + x) % D] += 1

        s = (s + k) % D
        dp = T

    print((dp[0] + (-1 if s != 0 else 0)) % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

K = map(int, list(input()))
D = int(input())

s = 0
dp = [0] * D
for k in K:
    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] += dpi
            T[(i + x) % D] % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)

Submission status: Time Limit Exceeded

Solution code:



from pprint import pprint 
from random import randint 

mod=10**9+7
def f(pos,d):
	dp=[[0]*d for _ in range(pos+1)]

	dp[0][0]=1
	for i in range(pos+1):
		for j in range(d):
			for k in range(10):
				dp[i][j]+=dp[i-1][(j-k)%d]
				if dp[i][j]>mod:
					dp[i][j]-=mod

	#dp[i][j] ways to get j as some using i+1 spots
	return dp 




def degit_sum(k,d):
	dp=f(len(k),d)
	# print(dp)
	size=len(k)
	t=0
	ans=0
	for i in range(size):
		dig=int(k[i])
		for j in range(dig):
			ans+=dp[size-i-1][(t-j)%d]
			if ans>mod:
				ans-=mod

		t=(t-dig)%d

	if  t%d==0:
		ans+=1
	return ans-1			
	


# for k in range(1,15):
# 	cnt=0
# 	s='70001'
# 	for i in range(1,int(s)+1):
# 		if sum(list(int(x) for x in str(i)))%k==0:
# 			cnt+=1
# 	if cnt!=degit_sum(s,k):
# 		print('k:',k,degit_sum(s,k),cnt)
# 		for i in range(1,101):
# 			if sum(list(int(x) for x in str(i)))%k==0:
# 				print('  ',i,end='')
# 		print()

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

res=degit_sum(k,d)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(100000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	x = totup(k)

	@lru_cache(None)
	def dfs(tight, i, tot):
		if i == len(x):
			return 1 if tot == 0 else 0
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(0, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(ntight, i + 1, (tot + dig) % d)
		return cnt % MOD

	ans += dfs(1, 0, 0) - 1
	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(10001)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	@lru_cache(None)
	def dfs(x, tight, i, tot):
		if i == len(x):
			return 1 if tot == 0 else 0
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(0, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(x, ntight, i + 1, (tot + dig) % d)
		return cnt % MOD

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	tupk = totup(k)
	ans += dfs(tupk, 1, 0, 0) - 1
	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(10000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	@lru_cache(None)
	def dfs(x, tight, i, tot):
		if i == len(x):
			return 1 if tot % d == 0 else 0
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(0, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(x, ntight, i + 1, tot + dig)
		return cnt % MOD

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	tupk = totup(k)
	ans += dfs(tupk, 1, 0, 0) - 1
	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(10000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	@lru_cache(None)
	def dfs(x, tight, i, tot):
		if i == len(x):
			return 1 if tot % d == 0 else 0
		start = 0 if i > 0 else 1
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(start, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(x, ntight, i + 1, tot + dig)
		return cnt % MOD

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	tupk = totup(k)
	ans += dfs(tupk, 1, 0, 0)
	for i in range(1, len(tupk)):
		bndry = 10**i-1
		ans += dfs(totup(bndry), 1, 0, 0)
		ans %= MOD

	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,s,e,d):
  if i==n:
    return s==0
  if (i,s,e) not in d:
    d[i,s,e]=sum(f(i+1,(s+j)%r,e and j==a[i],d) for j in xrange(a[i]+1 if e else 10))%(pow(10,9)+7)
  return d[i,s,e]
a=map(int,list(raw_input().strip()))
n=len(a)
r=input()
print (f(0,0,True,{})-1)%(pow(10,9)+7)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
n = int(input())
d = int(input())
p = 10**9+7
DP = {}
DP[-1] = [0]*d
DP[0] = [0]*d
DP[0][0] = 1
def dp(i):
    try:
        return DP[i]
    except:
        pass
    q, r = i//10, i % 10
    DP[i] = []
    for j in range(d):
        tmp = 0
        for k in range(r+1):
            tmp += dp(q)[(j-k) % d]
        for k in range(r+1, 10):
            tmp += dp(q-1)[(j-k) % d]
        DP[i].append(tmp % p)
    return DP[i]
print((dp(n)[0]-1) % p)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
n = int(input())
d = int(input())
p = 10**9+7
DP = {}
DP[-1] = [0]*d
DP[0] = [0]*d
DP[0][0] = 1
def dp(i):
    try:
        return DP[i]
    except:
        pass
    q, r = i//10, i % 10
    DP[i] = []
    for j in range(d):
        tmp = 0
        for k in range(r+1):
            tmp += dp(q)[(j-k) % d]
        for k in range(r+1, 10):
            tmp += dp(q-1)[(j-k) % d]
        DP[i].append(tmp)
    return DP[i]
print((dp(n)[0]-1) % p)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    K=input()
    D=I()
    N=len(str(K))
    
    #dp[i][j]はi桁目まで見て，総和のmodがj，tight&lose
    dpt=[[0]*D for _ in range(N+1)]
    dpl=[[0]*D for _ in range(N+1)]
    
    start=int(K[0])
    
    #初期化
    dpt[0][0]=1
            
    #推移
    for i in range(N):
        num=(int(K[i]))
        #t
        for j in range(D):
            if dpt[i][j]!=0:
                dpt[i+1][(j+num)%D]=1
                for k in range(num):
                    dpl[i+1][(j+k)%D]+=1
        #l
        for j in range(D):
            for k in range(10):
                dpl[i+1][(j+k)%D]+=dpl[i][j]
                
    #0もカウントしているmので1ひく
    print((dpt[-1][0]+dpl[-1][0]-1)%mod)
    
    
            
            
    
    

main()

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
D = int(input())
MOD = 10**9 + 7

dp = [[[0]*D for _ in range(2)] for _ in range(int(len(str(K)))+1)]
dp[0][0][0] = 1

for digit in range(int(len(str(K)))):
    for smaller_flg in [0,1]:
        for mod_d in range(D):
            lim = 9 if smaller_flg else int(str(K)[digit])
            for digit_num in range(lim+1):
                dp[digit+1][smaller_flg or digit_num < lim][(mod_d + digit_num)%D] += dp[digit][smaller_flg][mod_d]
                dp[digit+1][smaller_flg or digit_num < lim][(mod_d + digit_num)%D] %= MOD

print((dp[int(len(str(K)))][1][0] + dp[int(len(str(K)))][0][0] - 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
            DP1_[r] += DP1[(r-j) % d]
        DP0_[r] += DP0[(r-i) % d]
        DP1_[r] += DP1[(r-i) % d]
        for j in range(i+1, 10):
            DP0_[r] += DP0[(r-j) % d]
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print((DP1[0]-1+p) % p)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
D = int(input())
n = len(str(K))

mod = 10**9+7

s = str(K)

dp = [[[0, 0] for _ in range(D)] for _ in range(n+1)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(D):
        for k in range(2):
            nd = int(s[i])
            for d in range(10):
                ni = i+1
                nj = (j+d)%D
                nk = k
                if k == 0:
                    if d > nd:
                        continue
                    elif d < nd:
                        nk = 1
                    else:
                        pass
                dp[ni][nj][nk] += dp[i][j][k]%mod
print((dp[n][0][0]+dp[n][0][1]-1)%mod)

Submission status: Time Limit Exceeded

Solution code:
K = str(input())
D = int(input())

N = len(K)

MOD = 10 ** 9 + 7

# if D == 1:
#     print (K)
#     exit()
# elif D == 2:
#     print (int(K) // 2)
#     exit()
# elif D == 5:
#     print (int(K) // 5)

dp0 = [[0] * D for _ in range(N + 1)]
dp1 = [0] * (N + 1)

for i in range(N):
    next_ = int(K[i])
    tmp = dp1[i]

    dp1[i + 1] = (tmp + next_) % D
    
    for j in range(next_):
        dp0[i + 1][(tmp + j) % D] += 1
    # print (dp0[i + 1])
    for j in range(D):
        for k in range(10):
            dp0[i + 1][(j + k) % D] += dp0[i][j]
    
    for j in range(D):
        dp0[i + 1][j] %= MOD


# for tmp in dp0:
#     print (tmp)

# print (dp1)


ans = dp0[N][0] - 1
if dp1[N] == 0:
    ans += 1

print (ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
K=input()
D=int(input())
#余り0,余り1,余り2,…,余り(D-1)
dp=[0]*D
mod=10**9+7
s=0
for i in range(len(K)):
  ndp=[0]*D
  #余りがjだったものは(j+d)%Dの余りに変わるので
  for j in range(D):
    for d in range(10):
      ndp[(j+d)%D]=(ndp[(j+d)%D]+dp[j])%mod
  #直前までKと数字が同じだったものをカウント
  for d in range(int(K[i])):
    ndp[(s+d)%D]+=1 
  dp=ndp
  s=(s+int(K[i]))%D
#0000…の場合を引き、もしもKが該当するなら1を加える
ans=dp[0]-1
if s%D==0:
  ans+=1
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#if tight==1 it is not possible to go over k[idx]
#if tight==0 we can go from 0 to 9
import sys
sys.setrecursionlimit(10**5+1)
from functools import lru_cache
m = 10**9+7
@lru_cache(None)
def solve(idx,rem,tight):
    if idx==len(k):
        if rem==0:
            return 1
        return 0
    lim = 9 if tight==0 else int(k[idx])
    ans = 0
    for i in range(0,lim+1):
        curTight = tight 
        if i<int(k[idx]):
            curTight=0
        ans+=solve(idx+1,(rem+i)%d,curTight)
        ans%=m
    return ans
k = sys.stdin.readline().strip()
d = int(sys.stdin.readline().strip())
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
#if tight==1 it is not possible to go over k[idx]
#if tight==0 we can go from 0 to 9
import sys
sys.setrecursionlimit(10**5)
from functools import lru_cache
m = 10**9+7
@lru_cache(None)
def solve(idx,rem,tight):
    if idx==len(k):
        if rem==0:
            return 1
        return 0
    lim = 9 if tight==0 else int(k[idx])
    ans = 0
    for i in range(0,lim+1):
        curTight = tight 
        if i<int(k[idx]):
            curTight=0
        ans+=solve(idx+1,(rem+i)%d,curTight)
        ans%=m
    return ans
k = input().strip()
d = int(input())
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
#if tight==1 it is not possible to go over k[idx]
#if tight==0 we can go from 0 to 9
import sys
sys.setrecursionlimit(10**5+1)
from functools import lru_cache
m = 10**9+7
@lru_cache(None)
def solve(idx,rem,tight):
    if idx==len(k):
        if rem==0:
            return 1
        return 0
    lim = 9 if tight==0 else int(k[idx])
    ans = 0
    for i in range(0,lim+1):
        curTight = tight 
        if i<int(k[idx]):
            curTight=0
        ans+=solve(idx+1,(rem+i)%d,curTight)
        ans%=m
    return ans
k = input().strip()
d = int(input())
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def slv(K, D):
    rl = Counter()
    r = Counter()
    rl[0] = 1

    M = 10**9 + 7
    for c in K:
        d = int(c)
        rln = Counter()
        rn = Counter()
        for rem, count in rl.items():
            rln[(rem + d) % D] += count
            rln[(rem + d) % D] %= M

        for rem, count in rl.items():
            for i in range(d):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        for rem, count in r.items():
            for i in range(10):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        rl = rln
        r = rn
    return (rl[0] + r[0] - 1) % M


K = input()
D = int(input())
print(slv(K, D))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline


def main():
    def digit_dp(n, m):
        # dp[i][j][k] -> i: 現在見ている桁数
        #                j: n以下が保証されているかどうか
        #                k: m で割った余りの総和
        n = list(map(int, list(str(n))))
        n_len = len(n)
        dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
        dp_table[0][0][0] = 1

        for j in range(2):
            for i in range(n_len):
                for d in range(0, 10 if j else n[i] + 1):
                    for k in range(m):
                        dp_table[i + 1][j or (d < n[i])][(k + d % m) % m] += dp_table[i][j][k]

        return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
        #0 の分、1を減算


    a = int(readline())
    b = int(readline())
    mod = 10**9 + 7
    print(digit_dp(a, b) % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline

def main():
    def digit_dp(n, m):
        # dp[i][j][k] -> i: 現在見ている桁数
        #                j: n以下が保証されているかどうか
        #                k: m で割った余りの総和
        n = list(map(int, list(str(n))))
        n_len = len(n)
        dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
        dp_table[0][0][0] = 1

        for i in range(n_len):
            for j in range(2):
                for k in range(m):
                    for d in range(0, 10 if j else n[i] + 1):
                        dp_table[i + 1][j or (d < n[i])][(k + d) % m] += dp_table[i][j][k]

        return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
        #0 の分、1を減算


    a = int(readline())
    b = int(readline())
    mod = 10**9 + 7
    print(digit_dp(a, b) % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline

def main():
    def digit_dp(n, m):
        # dp[i][j][k] -> i: 現在見ている桁数
        #                j: n以下が保証されているかどうか
        #                k: m で割った余りの総和
        n = list(map(int, list(str(n))))
        n_len = len(n)
        dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
        dp_table[0][0][0] = 1

        for i in range(n_len):
            for j in range(2):
                for k in range(m):
                    for d in range(0, 10 if j else n[i] + 1):
                        dp_table[i + 1][j or (d < n[i])][(k + d % m) % m] += dp_table[i][j][k]

        return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
        #0 の分、1を減算


    a = int(readline())
    b = int(readline())
    mod = 10**9 + 7
    print(digit_dp(a, b) % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def digit_dp(n, m):
    # dp[i][j][k] -> i: 現在見ている桁数
    #                j: n以下が保証されているかどうか
    #                k: m で割った余りの総和
    n = list(map(int, list(str(n))))
    n_len = len(n)
    dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
    dp_table[0][0][0] = 1

    for i in range(n_len):
        for j in range(2):
            for k in range(m):
                for d in range(0, 10 if j else n[i] + 1):
                    dp_table[i + 1][j or (d < n[i])][(k + d % m) % m] += dp_table[i][j][k]

    return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
    #0 の分、1を減算


a = int(input())
b = int(input())
mod = 10**9 + 7
print(digit_dp(a, b) % mod)

Submission status: Time Limit Exceeded

Solution code:
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)] 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(dp[0][0][1] - 1)
# print(dp)
# for i in dp:
#     for s in i:
#         for border in s:
#             print(border, end=" ")
#         print()
#     print("-----")

def count(v):
    cnt = 0
    while v:
        cnt += v % 10
        v //= 10
    return cnt

ans = 0
for i in range(1, k + 1):
    if count(i) % d == 0:
        ans += 1
print(ans)