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: Wrong Answer

Solution code:
d = int(input())
n = input()
t = len(n)
mod = 10**9 + 7
dp1 = [[0 for i in range(d)] for j in range(t)]
dp2 = [[0 for i in range(d)] for j in range(t)]

dp1[0][int(n[0])%d] += 1
for i in range(int(n[0])):
    dp2[0][i%d] += 1
    
for i in range(1,t):
    now = int(n[i])
    for j in range(10):
        if j == now:
            for k in range(d):
                dp1[i][(k+j)%d] += dp1[i-1][k]
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp1[i][(k+j)%d] %= mod
                dp2[i][(k+j)%d] %= mod
        elif j < now:
            for k in range(d):
                dp2[i][(k+j)%d] += dp1[i-1][k]
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp2[i][(k+j)%d] %= mod
        else:
            for k in range(d):
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp2[i][(k+j)%d] %= mod

print((dp1[-1][0]+dp2[-1][0]-1)%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def a_int(): return int(read())


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

K = np.array(list(map(int, list(input()))))
D = a_int()

'''
ある数xにおいて総和がDの倍数であるかの判定
x[0]+x[1]...+x[n] ≡ 0 (mod D) 各桁の和にMODを取れば良い。つまり桁ごとに処理できる

dp[i,j,k] ... K[:i]以下の整数のうち、k=mod Dとなるような数字の個数。j==1は上位桁が一致している場合の通りの個数。j==0は上位桁が一致しなくなったときの個数。

遷移
for l in range(10):
    dp[i+1,0,(k+l)%D] += dp[i,0,k] #1~9を考慮可能
for l in range(K[i]):
    dp[i+1,0,(k+l)%D] += dp[i,1,k] #1~K[i]-1をつけるとぴったりにならないグループへ行く

dp[i+1,1,(k+K[i])%D] += dp[i,1,k]
'''
# print(K, D)

from numba import njit


@njit('(i8[:],i8)', cache=True)
def solve(K, D):
    N = K.shape[0]
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0, 1, 0] = 1
    for i in range(N):  # 各桁について
        for k in range(D):  # 各あまりについて処理
            for l in range(10):  # 各数字について処理
                dp[i + 1, 0, (k + l) % D] += dp[i, 0, k]  # 1~9を考慮可能
                if l < K[i]:
                    dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]  # 1~9を考慮可能
                    # 1~K[i]-1をつけるとぴったりにならないグループへ行く
                dp[i + 1, 0, (k + l) % D] %= MOD
            # ぴったりグループ
            dp[i + 1, 1, (k + K[i]) % D] += dp[i, 1, k]
            dp[i + 1, 1, (k + K[i]) % D] %= MOD

    print(dp[-1, :, 0].sum() % MOD - 1)  # -1は0の分


solve(K, D)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def a_int(): return int(read())


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

K = np.array(list(map(int, list(input()))))
D = a_int()

'''
ある数xにおいて総和がDの倍数であるかの判定
x[0]+x[1]...+x[n] ≡ 0 (mod D) 各桁の和にMODを取れば良い。つまり桁ごとに処理できる

dp[i,j,k] ... K[:i]以下の整数のうち、k=mod Dとなるような数字の個数。j==1は上位桁が一致している場合の通りの個数。j==0は上位桁が一致しなくなったときの個数。

遷移
for l in range(10):
    dp[i+1,0,(k+l)%D] += dp[i,0,k] #1~9を考慮可能
for l in range(K[i]):
    dp[i+1,0,(k+l)%D] += dp[i,1,k] #1~K[i]-1をつけるとぴったりにならないグループへ行く

dp[i+1,1,(k+K[i])%D] += dp[i,1,k]
'''
# print(K, D)

from numba import njit


@njit('(i8[:],i8)', cache=True)
def solve(K, D):
    N = K.shape[0]
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0, 1, 0] = 1
    for i in range(N):  # 各桁について
        for k in range(D):  # 各あまりについて処理
            for l in range(10):  # 各数字について処理
                dp[i + 1, 0, (k + l) % D] += dp[i, 0, k]  # 1~9を考慮可能
                dp[i + 1, 0, (k + l) % D] %= MOD
            for l in range(K[i]):
                # 1~K[i]-1をつけるとぴったりにならないグループへ行く
                dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]
                dp[i + 1, 0, (k + l) % D] %= MOD
            dp[i + 1, 1, (k + K[i]) % D] += dp[i, 1, k]
            dp[i + 1, 1, (k + K[i]) % D] %= MOD

    # print(dp)
    print(dp[-1, :, 0].sum() % MOD - 1)  # -1は0の分


solve(K, D)

Submission status: Wrong Answer

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
    
    if D == 2:
        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: Wrong Answer

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
    
    if D == 2:
        sub = 0
        for i in range(n):
            sub = (sub+int(K[i]))%D
        if sub == 0:
            dp[n][0] += 1
            
    
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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()
    
    if D == 2:
        ans = 0
        sub = 0
        for i in range(n):
            k = int(K[i])
            if i == n-1:
                k = k//2*2
            ans = (ans*10+sub+k//2)%mod
            sub = 5 if k%2 else 0
        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
        
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
        
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    print(dp)
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

K = S()
D = I()

N = len(K)

dp = [[0 for i in range(D)] for k in range(N+1)]
dp[0][0] = 1
for k in range(N):
  for i in range(D):
    for j in range(10):
      dp[k+1][(i+j)%D] += dp[k][i]
      dp[k+1][(i+j)%D] %= MOD

ans = 0
carry = 0
for i in range(N):
  s = int(K[i])
  for j in range(s):
    ans += dp[N-1-i][(-carry-j)%D]
    ans %= MOD
  carry += s
  carry %= D

print(ans-1+int(carry==0))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

K = S()
D = I()

N = len(K)

dp = [[0 for i in range(D)] for k in range(N+1)]
dp[0][0] = 1
for k in range(N):
  for i in range(D):
    for j in range(10):
      dp[k+1][(i+j)%D] += dp[k][i]
      dp[k+1][(i+j)%D] %= MOD

ans = 0
carry = 0
for i in range(N):
  s = int(K[i])
  for j in range(s):
    ans += dp[N-1-i][(-carry-j)%D]
    ans %= MOD
  carry += s
  carry %= D
print(ans-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

K = S()
D = I()

N = len(K)

dp = [[0 for i in range(D)] for k in range(N+1)]
dp[0][0] = 1
for k in range(N):
  for i in range(D):
    for j in range(10):
      dp[k+1][(i+j)%D] += dp[k][i]
      dp[k+1][(i+j)%D] %= MOD

ans = 0
carry = 0
for i in range(N):
  s = int(K[i])
  for j in range(s):
    ans += dp[N-1-i][(-carry-j)%D]
    ans %= MOD
  carry += s
  carry %= D
print(ans-int(D!=1))

Submission status: Wrong Answer

Solution code:
def solve(K, D):
    N = len(K)
    MOD = 1_000_000_007
    dp = [[[0] * D for _ in range(2)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for is_less in range(2):
            for k in range(D):
                for l in range(10 if is_less else K[i] + 1):
                    is_less_ = is_less or l < K[i]
                    k_ = (k + l) % D
                    dp[i + 1][is_less_][k_] += dp[i][is_less][k]
                    dp[i + 1][is_less_][k_] %= MOD
    return dp[N][0][0] + dp[N][1][0] - 1


print(solve(list(map(int, input())), int(input())))

Submission status: Wrong Answer

Solution code:
from numba import njit
import numpy as np


@njit("i8(i8[:],i8)")
def solve(K, D):
    N = len(K)
    MOD = 1_000_000_007
    dp = [[[0] * D for _ in range(2)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for is_less in range(2):
            for k in range(D):
                for l in range(10 if is_less else K[i] + 1):
                    is_less_ = is_less or l < K[i]
                    k_ = (k + l) % D
                    dp[i + 1][is_less_][k_] += dp[i][is_less][k]
                    dp[i + 1][is_less_][k_] %= MOD
    return dp[N][0][0] + dp[N][1][0] - 1


print(solve(np.array(list(map(int, input()))), int(input())))

Submission status: Wrong Answer

Solution code:
K = list(map(int, input()))
N = len(K)
D = int(input())
MOD = 1_000_000_007

dp = [[[0] * D for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 1
for i in range(N):
    for is_less in range(2):
        for k in range(D):
            for l in range(10 if is_less else K[i] + 1):
                is_less_ = is_less or l < K[i]
                k_ = (k + l) % D
                dp[i + 1][is_less_][k_] += dp[i][is_less][k]
                dp[i + 1][is_less_][k_] %= MOD
print(dp[N][0][0] + dp[N][1][0] - 1)

Submission status: Wrong Answer

Solution code:
K=int(input())
D=int(input())
li=[]
for i in range(1,10):
    if(D*i<=9):
        li.append(D*i)
x=K//9
count=0

for i in li:
    if(x*9+i>K):count+=1
# print(x)
# print(li)
# print(count)
print((x+1)*len(li)-count)

Submission status: Wrong Answer

Solution code:
k=input()
n=len(k)
d=int(input())
mod=10**9+7
dp=[[[0]*2 for _ in range(d)] for i in range(n)]
for num in range(int(k[0])+1):
    if num==int(k[0]):
        dp[0][num%d][0]=1
    else:
        dp[0][num%d][1]=1
for i in range(1,n):
    num=int(k[i])
    for l in range(10):
        for j in range(d):
            if l<num:
                dp[i][(j+l)%d][1]+=dp[i-1][j][0]
            elif l==num:
                dp[i][(j+l)%d][0]+=dp[i-1][j][0]
            dp[i][(j+l)%d][1]+=dp[i-1][j][1]
            dp[i][(j+l)%d][1]%=mod
            dp[i][(j+l)%d][0]%=mod
print((sum(dp[n-1][0])-1+mod)%mod)

Submission status: Wrong Answer

Solution code:
k=input()
n=len(k)
d=int(input())
mod=10**9+7
dp=[[[0]*2 for _ in range(d)] for i in range(n)]
for num in range(int(k[0])+1):
    if num==int(k[0]):
        dp[0][num%d][0]=1
    else:
        dp[0][num%d][1]=1
for i in range(1,n):
    num=int(k[i])
    for l in range(10):
        for j in range(d):
            if l<num:
                dp[i][(j+l)%d][1]+=dp[i-1][j][0]
            elif l==num:
                dp[i][(j+l)%d][0]+=dp[i-1][j][0]
            dp[i][(j+l)%d][1]+=dp[i-1][j][1]
            dp[i][(j+l)%d][1]%=mod
            dp[i][(j+l)%d][0]%=mod
print((sum(dp[n-1][0])-1)%mod)

Submission status: Wrong Answer

Solution code:
k=input()
n=len(k)
d=int(input())
mod=10**9+7
dp=[[[0]*2 for _ in range(d)] for i in range(n)]
for num in range(int(k[0])+1):
    if num==int(k[0]):
        dp[0][num%d][0]=1
    else:
        dp[0][num%d][1]=1
for i in range(1,n):
    num=int(k[i])
    for l in range(10):
        for j in range(d):
            if l<num:
                dp[i][(j+l)%d][1]+=dp[i-1][j][0]
            elif l==num:
                dp[i][(j+l)%d][0]+=dp[i-1][j][0]
            dp[i][(j+l)%d][1]+=dp[i-1][j][1]
            dp[i][(j+l)%d][1]%=mod
            dp[i][(j+l)%d][0]%=mod
print(sum(dp[n-1][0])-1)

Submission status: Wrong Answer

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]) % DIV - 1) # 0を数えないので引く

Submission status: Wrong Answer

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) # 0を数えないので引く

Submission status: Wrong Answer

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

DP = [[[0] * 2 for _ in range(D)] for _ in range(len(K))]

for i in range(K[0]):
  DP[0][i % D][0] = 1
DP[0][K[0] % D][1] = 1

for i in range(1, len(K)):
  for j in range(10):
    for k in range(D):
      DP[i][(j + k) % D][0] = (DP[i][(j + k) % D][0] + DP[i - 1][k][0]) % MOD
  for j in range(K[i]):
    for k in range(D):
      DP[i][(j + k) % D][0] = (DP[i][(j + k) % D][0] + DP[i - 1][k][1]) % MOD
  for k in range(D):
    DP[i][(k + K[i]) % D][1] = (DP[i][(k + K[i]) % D][1] + DP[i - 1][k][1]) % MOD

ans = (DP[-1][0][0] + DP[-1][0][1] - 1) % MOD
while ans < 0:
  ans += MOD

print(ans)

Submission status: Wrong Answer

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

DP = [[[0] * 2 for _ in range(D)] for _ in range(len(K))]

for i in range(K[0]):
  DP[0][i % D][0] = 1
DP[0][K[0] % D][1] = 1

for i in range(1, len(K)):
  for j in range(10):
    for k in range(D):
      DP[i][(j + k) % D][0] = (DP[i][(j + k) % D][0] + DP[i - 1][k][0]) % MOD
  for j in range(K[i]):
    for k in range(D):
      DP[i][(j + k) % D][0] = (DP[i][(j + k) % D][0] + DP[i - 1][k][1]) % MOD
  for k in range(D):
    DP[i][(k + K[i]) % D][1] = (DP[i][(k + K[i]) % D][1] + DP[i - 1][k][1]) % MOD

ans = DP[-1][0][0] + DP[-1][0][1] - 1

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
k = input()
d = int(input())
dp = [0] * d
now = 0
for i in map(int, k):
    ndp = [0] * d
    for t in range(i):
        ndp[(now+t) % d] = (ndp[(now+t) % d] + 1) % MOD
    for j in range(d):
        for t in range(10):
            ndp[(j+t) % d] = (ndp[(j+t) % d] + dp[j]) % MOD
    now = (now + i) % d
    dp = ndp
print(dp[0] - 1 + (now == 0))