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: Accepted

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~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() - 1) % MOD)  # -1は0の分


solve(K, D)

Submission status: Accepted

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() - 1) % MOD)  # -1は0の分


solve(K, D)

Submission status: Accepted

Solution code:
k=input()
d=int(input())
l=len(k)
N=10**9 + 7
dp=[[[0]*2 for _ in range(d+5)] for i in range(l+5)]
prefs=[int(k[0])%d]
for i in range(1,l):
    prefs.append((prefs[i-1]+int(k[i]))%d)
for i in range(0,int(k[0])):
    dp[0][i%d][1]+=1
dp[0][int(k[0])%d][0]+=1
for i in range(1,l):
    for r in range(d):
        for dig in range(10):
            dp[i][r][1]=(dp[i][r][1]+dp[i-1][(r-dig+d)%d][1])%N
        for dig in range(0,int(k[i])):
            dp[i][r][1] = (dp[i][r][1] + dp[i - 1][(r - dig + d) % d][0]) % N
        if prefs[i]==r:
            dp[i][r][0]=(dp[i][r][0]+1)%N
print((dp[l-1][0][1]+dp[l-1][0][0]-1+N)%N)

Submission status: Accepted

Solution code:
import math

K=input()
D=int(input())
n=len(K)
dp=[[[0 for _ in range(D)] for _ in range(2)] for _ in range(n+1)]
MOD=10**9+7

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

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

Submission status: Accepted

Solution code:
mod=10**9+7
k=input()
d=int(input())

dp=[[[0]*2 for i in range(d)] for j in range(len(k)+1)]
dp[0][0][0]=1

for i in range(len(k)):
  x=int(k[i])
  for j in range(d):
    dp[i+1][(j+x)%d][0]+=dp[i][j][0]
    dp[i+1][(j+x)%d][0]%=mod
    for z in range(10):
      dp[i+1][(j+z)%d][1]+=dp[i][j][1]
      dp[i+1][(j+z)%d][1]%=mod
    
    for y in range(x):
      dp[i+1][(j+y)%d][1]+=dp[i][j][0]
      dp[i+1][(j+y)%d][1]%=mod
      

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

Submission status: Accepted

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 f in range(2)] for k in range(N+1)]
dp[0][0][0] = 1
for k in range(N):
  s = int(K[k])
  for i in range(D):
    for j in range(10):
      dp[k+1][1][(i+j)%D] += dp[k][1][i]
      dp[k+1][1][(i+j)%D] %= MOD
    for j in range(s):
      dp[k+1][1][(i+j)%D] += dp[k][0][i]
      dp[k+1][1][(i+j)%D] %= MOD
    dp[k+1][0][(i+s)%D] += dp[k][0][i]
    dp[k+1][0][(i+s)%D] %= MOD

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

Submission status: Accepted

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))%MOD)

Submission status: Accepted

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][k] + dp[i-1][1][(k-j) % D]) % mod
        for j in range(int(K[i-1])):
            dp[i][1][k] = (dp[i][1][k] + dp[i-1][0][(k-j) % D]) % mod
        dp[i][0][k] = (dp[i][0][k] + dp[i-1][0][(k-int(K[i-1])) % D]) % mod

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

Submission status: Accepted

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.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(n)
    for i in range(l):
        max_d = int(n[i])
        for j in range(2):
            for ki in range(f):
                for di in range(10 if j else max_d + 1):
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] += dp[i][j][ki]
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


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

Submission status: Accepted

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(n)
    for i in range(l):
        max_d = int(n[i])
        for j in range(2):
            for ki in range(f):
                for di in range(10 if j else max_d + 1):
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] += dp[i][j][ki]
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = input()
d = int(input())
print(digit_dp(k, d) % mod)

Submission status: Accepted

Solution code:
# 25:27
import numpy as np
from numba import njit


@njit("i8(i8[:],i8)")
def solve(K, D):
    N = len(K)
    MOD = 1_000_000_007
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    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) % MOD


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

Submission status: Accepted

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) % MOD


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

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	K = rll()[0]
	D = int(rl())
	lim = []
	for c in K: lim.append(int(c))
	n = len(lim)
	dp = [[[0]*D for j in range(2)] for i in range(n+1)]
	dp[0][1][0] = 1
	for i in range(n):
		for tight in range(2):
			for ds in range(D):
				md = lim[i] if tight else 9
				for d in range(md+1):
					nt = 1 if tight and lim[i] == d else 0
					nds = (d + ds) % D
					dp[i+1][nt][nds] += dp[i][tight][ds]
					dp[i+1][nt][nds] %= MOD
	ans = (dp[n][0][0] + dp[n][1][0] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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: Accepted

Solution code:
def solve():
  K = list(map(int,list(input())))
  digit = len(K)
  D = int(input())
  dp = [[[0]*D for _ in range(2)] for _ in range(digit+1)]
  dp[0][1][0] = 1
  mod = 10**9+7
  for k in range(1,digit+1):
    for d in range(D):
      dp[k][1][d] = dp[k-1][1][(d-K[k-1])%D]
      for p in range(10):
        dp[k][0][d] += dp[k-1][0][(d-p)%D] 
      for p in range(K[k-1]):
        dp[k][0][d] += dp[k-1][1][(d-p)%D]
      dp[k][0][d] %= mod
  ans = (dp[-1][0][0]+dp[-1][1][0]-1)%mod
  return ans
print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


K = ns()
D = ni()

dp = [0] * D
mod = 10 ** 9 + 7
now_mod = 0

for k in K:
    k = int(k)
    dp_old = dp
    dp = [0] * D
    for kk in range(k):
        dp[(now_mod+kk) % D] += 1
    now_mod = (now_mod + k) % D
    for i, d in enumerate(dp_old):
        for n in range(10):
            dp[(i+n) % D] += d
            dp[(i+n) % D] %= mod
    # print(now_mod, dp)
if now_mod == 0:
    dp[0] += 1
print((dp[0]-1) % mod)

Submission status: Accepted

Solution code:
k = input()
d = int(input())
n = len(k)
mod = 10**9 + 7

MOD = [[0] * 10 for i in range(n)]
# for i in range(1, 10):
#     MOD[0][i] = (MOD[0][i-1] + 1) % d
# for i in range(1, n):
#     for j in range(10):
#         MOD[i][j] = (MOD[i-1][j] * 10) % d

for i in range(n):
    for j in range(10):
        MOD[i][j] = j % d

D = [0] * d
h = 0
for i in range(int(k[0])):
    D[MOD[n-1][i]] += 1
h = MOD[n-1][int(k[0])]

for i in range(1, n):
    # print(D)
    DN = [0] * d
    for j in range(10):
        for l in range(d):
            DN[(l + MOD[n-1-i][j]) % d] = (DN[(l + MOD[n-1-i][j]) % d] + D[l]) % mod
    for j in range(int(k[i])):
        DN[(h + MOD[n-1-i][j]) % d] = (DN[(h + MOD[n-1-i][j]) % d] + 1) % mod
    h = (h + MOD[n-1-i][int(k[i])]) % d
    D = DN[:]
# print(D)

D[h] += 1
# print(D)
print((D[0] - 1) % mod)

Submission status: Accepted

Solution code:

def resolve():
    MOD = 10**9+7
    K = input()
    D = int(input())
    N = len(K)

    # dp[keta][D][smaler]
    dp = [[[0]*2 for _ in range(D)] for _ in range(N+1)]
    dp[0][0][0] = 1

    for i in range(N):
        for d in range(D):
            # smaller=1 どの数字も使用できる
            for k in range(10):
                dp[i + 1][(d + k) % D][1] += dp[i][d][1]
                dp[i + 1][(d + k) % D][1] %= MOD

            # smaller=0 K[i]未満の数字のみ使用できる
            # 次の遷移は繰り上げが無いのでどの数字も使用できる。smaller = 1
            num = int(K[i])
            for k in range(num):
                dp[i + 1][(d + k) % D][1] += dp[i][d][0]
                dp[i + 1][(d + k) % D][1] %= MOD

            dp[i + 1][(d + num) % D][0] += dp[i][d][0]
            dp[i + 1][(d + num) % D][0] %= MOD


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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    MOD = 10**9+7
    K = input()
    D = int(input())
    N = len(K)

    # dp[keta][D][smaler]
    dp = [[[0]*2 for _ in range(D)] for _ in range(N+1)]
    dp[0][0][0] = 1

    for i in range(N):
        num = int(K[i])
        for j in range(D):
            for smaller in range(2):
                for d in range(10):
                    ni = i+1
                    nsmaller = smaller
                    nj = (j+d)%D
                    if smaller == 0:
                        if d < num:
                            nsmaller = 1
                        if d > num:
                            continue
                    dp[ni][nj][nsmaller] += dp[i][j][smaller]
                    dp[ni][nj][nsmaller] %= MOD
    print((dp[N][0][1] + dp[N][0][0] - 1) % MOD)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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: Accepted

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)) % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(K, D):
    K = [x - ord("0") for x in K]
    N = len(K)
    less = [[0] * D for i in range(N + 1)]
    border = 0
    debug(": K, N", K, N)
    debug(": less", less)
    for i in range(N):
        for j in range(10):
            for d in range(D):
                less[i][(d + j) % D] += less[i - 1][d]
                less[i][(d + j) % D] %= MOD
            if j < K[i]:
                less[i][(border + j) % D] += 1
        border += K[i]
        border %= D

    debug(": less", less)
    ret = less[N - 1][0] - 1
    ret += (border == 0)
    return ret % MOD


def main():
    # parse input
    K = input().strip()
    D = int(input())
    print(solve(K, D))


# tests
T1 = """
30
4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    6
    """


T2 = """
1000000009
1
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    2
    """


T3 = """
98765432109876543210
58
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    635270834
    """


T4 = """
555
1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    555
    """


T6 = """
5
1
"""


def test_T6():
    """
    >>> as_input(T6)
    >>> main()
    5
    """

# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


k = input()
n = len(k)
d = int(input())
dp0 = [[0]*(d) for _ in range(n+1)]
dp1 = [[0]*(d) for _ in range(n+1)]
dp1[0][0] = 1
M = 10**9+7
for i in range(1,n+1):
    for j in range(d):
        v = int(k[i-1])
        dp1[i][j] = dp1[i-1][(j-v)%d]
        for vv in range(10):
            if vv<v:
                dp0[i][j] += dp1[i-1][(j-vv)%d]
            dp0[i][j] += dp0[i-1][(j-vv)%d]
        dp1[i][j] %= M
        dp0[i][j] %= M
ans = (dp0[n][0]+dp1[n][0]-1) % M
print(ans)

Submission status: Accepted

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

dp = [[[0]*D for _ in range(2)] for _ in range(L+1)]
# dp[i][j][d] = num of "up to i-th, j = less than flag, d mod = d"
dp[0][0][0] = 1

for i in range(1, L+1):
    a = int(K[i-1])
    for d in range(D):
        dp[i][0][(d+a)%D] += dp[i-1][0][d]
        dp[i][0][(d+a)%D] %= MOD
        for b in range(10):
            dp[i][1][(d+b)%D] += dp[i-1][1][d] + (b<a)*dp[i-1][0][d]
            dp[i][1][(d+b)%D] %= MOD

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

Submission status: Accepted

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

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

    maxD = len(strN)

    dpLt = [0] * D
    NmodD = 0
    for d, Nd in enumerate(strN):
        Nd = int(Nd)
        dpLt2 = [0] * D
        for modD in range(D):
            dpLt[modD] = dpNow = dpLt[modD] % MOD
            for x in range(10):
                modD2 = (modD+x) % D
                dpLt2[modD2] += dpNow
        for x in range(Nd):
            modD2 = (NmodD+x) % D
            dpLt2[modD2] += 1
        NmodD = (NmodD+Nd) % D
        dpLt = dpLt2

    print((dpLt[0] + (NmodD == 0) - 1) % MOD)


solve()

Submission status: Accepted

Solution code:
k = input()
d = int(input())
mod = 10**9+7

dp = [[[0]*2 for i in range(d)] for j in range(len(k)+1)]

dp[0][0][1] = 1
for i in range(len(k)):
    s = int(k[i])
    for j in range(10):
        for m in range(d):
            if s == j:
                dp[i+1][(m+j)%d][1] += dp[i][m][1]
                dp[i+1][(m+j)%d][1] %= mod
            elif s > j:
                dp[i+1][(m+j)%d][0] += dp[i][m][1]
                dp[i+1][(m+j)%d][0] %= mod
            dp[i+1][(m+j)%d][0] += dp[i][m][0]
            dp[i+1][(m+j)%d][0] %= mod

print((sum(dp[-1][0])-1)%mod)