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:
k = input()
d = int(input())
mod = 10**9+7
if d == 1:
    print(int(k)%mod)
    exit()
dp = [[[0]*2 for i in range(d)] for j in range(len(k))]
## dp[][][0] k 以下確定 [1] 未定

s = int(k[0])
dp[0][s%d][1] = 1
for i in range(s):
    dp[0][i%d][0] = 1

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

print((ans-1)%mod)

Submission status: Accepted

Solution code:
M=10**9+7
n=input()
d=int(input())
dp=[[[0,0] for j in range(d)] for i in range(len(n)+1)]
dp[0][0][0]=1
for i,x in enumerate(map(int,n),1):
  for j in range(10):
    for k in range(d):
      dp[i][(j+k)%d][1]+=dp[i-1][k][1]
      dp[i][(j+k)%d][1]%=M
      if j<x:
        dp[i][(j+k)%d][1]+=dp[i-1][k][0]
        dp[i][(j+k)%d][1]%=M
      if j==x:
        dp[i][(j+k)%d][0]+=dp[i-1][k][0]
        dp[i][(j+k)%d][0]%=M
print((sum(dp[-1][0])-1)%M)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    _ _ 

    dp[i][j][one_of_previous_number_is_lower] = count of remainder j up to i-th digit, 0 <= j < D

    dp[i][(j+digit)%D][True] += dp[i-1][j][True] + dp[i-1][j][False] digit < K[i]
    dp[i][(j+digit)%D][False] += dp[i-1][j][False]        digit == K[i]
    """
    K = list(map(int, input().strip()))
    D = read_int()
    dp = [[0, 0] for _ in range(D)]
    dp[0][0] = 1
    modulo = 10**9+7
    for i in range(len(K)):
        new_dp = [[0, 0] for _ in range(D)]
        for j in range(D):
            for digit in range(10):
                new_dp[(j+digit)%D][True] += dp[j][True]
                if digit < K[i]:
                    new_dp[(j+digit)%D][True] += dp[j][False]
                if digit == K[i]:
                    new_dp[(j+digit)%D][False] += dp[j][False]
                new_dp[(j+digit)%D][False] %= modulo
                new_dp[(j+digit)%D][True] %= modulo
        dp = new_dp
    return (dp[0][0]+dp[0][1]-1)%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    _ _ 

    dp[i][j][one_of_previous_number_is_lower] = count of remainder j up to i-th digit, 0 <= j < D

    dp[i][(j+digit)%D][True] += dp[i-1][j][True] + dp[i-1][j][False] digit < K[i]
    dp[i][(j+digit)%D][False] += dp[i-1][j][False]        digit == K[i]
    """
    K = list(map(int, input().strip()))
    D = read_int()
    dp = [[[0, 0] for _ in range(D)]
           for _ in range(len(K)+1)]
    dp[0][0][0] = 1
    modulo = 10**9+7
    for i in range(len(K)):
        for j in range(D):
            for digit in range(10):
                dp[i+1][(j+digit)%D][True] += dp[i][j][True]
                if digit < K[i]:
                    dp[i+1][(j+digit)%D][True] += dp[i][j][False]
                if digit == K[i]:
                    dp[i+1][(j+digit)%D][False] += dp[i][j][False]
                dp[i+1][(j+digit)%D][False] %= modulo
                dp[i+1][(j+digit)%D][True] %= modulo
    return (dp[-1][0][0]+dp[-1][0][1]-1)%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
def add(a, b):
    mod = 1e9+7
    c = a + b
    if c >= mod:
        c -= mod
    return c
def subtract(a, b):
    mod = 1e9+7
    c = a - b
    if c < 0:
        c += mod
    return c

K = input()

D = int(input())

# dp[sum][smaller_already] - no. of ways to have digits sum % D = sum, smaller_already means if it is already less than K

dp = [[0 for _ in range(2)] for _ in range(D)]

str_len = len(K)

dp[0][0] = 1

for where in range(str_len):
    new_dp = [[0 for _ in range(2)] for _ in range(D)]
    for sum_so_far in range(D):
        for smaller_already in [0, 1]:
            for digit in range(10):
                K_digit = ord(K[where]) - ord('0')
                if digit > K_digit and smaller_already == 0:
                    break
                new_sum = (sum_so_far + digit) % D
                new_smaller = 1 if smaller_already == 1 or digit < K_digit else 0
                new_dp[new_sum][new_smaller] = add(new_dp[new_sum][new_smaller], dp[sum_so_far][smaller_already])
    dp = new_dp
                
                
answer = add(dp[0][0], dp[0][1])

answer = int(subtract(answer, 1))

print(answer)


"""
#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

/*
30
4

brute-force -> look one by one -> from 1 to 30 -> if the digit sum is multiple of 4, then add
O(K * log K)


dp[d] - how many ways to get to remainder is d

dp[0] is the ans

dp[d] - how many ways to get to digit_sum as d

*/


int add(int a, int b) {
    const int mod = 1e9+7;
    int c = a + b;
    if (c >= mod) {
        c -= mod;
    }
    return c;
}

int subtract(int a, int b) {
    const int mod = 1e9+7;
    int c = a - b;
    if (c < 0) {
        c += mod;
    }
    return c;
}

int main() {
    const int nax = 10123;
    char K[nax];
    int D;
    scanf("%s", K);
    scanf("%d", &D);
    int len = strlen(K);
    vector<vector<int>> dp(D, vector<int>(2));
    // dp[sum][smaller_already] - no. of ways to choose digits so far
    // such that digits sum % D = sum and smaller_already means if the number
    // is already less than K
    dp[0][0] = 1;
    
    for (int where = 0; where < len; where++) {
        vector<vector<int>> new_dp(D, vector<int>(2));
        for (int sum = 0; sum < D; sum++) {
            for (bool sm_already : {false, true}) {
                for (int digit = 0; digit < 10; digit++) {
                    if (digit > K[where] - '0' && !sm_already) {
                        break;
                    }
                    int new_sum = (sum + digit) % D;
                    bool smaller = sm_already || digit < (K[where] - '0');
                    new_dp[new_sum][smaller] = add(new_dp[new_sum][smaller], dp[sum][sm_already]);
                }
            }
        }
        dp = new_dp;
    }
    
    int answer = add(dp[0][false], dp[0][true]);
    
    answer = subtract(answer, 1);
    
    printf("%d", answer);
    /*
    int ans = 0;
    for (int i = 1; i <= K; i++) {
        if (digit_sum(i) % D == 0) {
            ans += 1;
        }
    }
    printf("%d", ans);
    */
    
}
"""

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

K = map(int, 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, d):
            ndp[i % D] += dpi

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

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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

K = map(int, 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: Accepted

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

    K = map(int, 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)

main()

Submission status: Accepted

Solution code:
def main():
    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)

main()

Submission status: Accepted

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

MOD = 10**9+7
N = len(K)

# dp[i][j][k] := 上から i まで見て余りが j であり、
# k = 0 -> K ちょうど
# k = 1 -> K より小さい
# ようなものの数
dp = [[[0]*2 for _ in range(D)] for _ in range(N+1)] 
dp[0][0][0] = 1
for i in range(N):
    k = int(K[i])
    for j in range(D):
        dp[i+1][(j+k)%D][0] = dp[i][j][0]
        dp[i+1][(j+k)%D][0] %= MOD
        for d in range(10):
            dp[i+1][(j+d)%D][1] += dp[i][j][1]
            if d < k:
                dp[i+1][(j+d)%D][1] += dp[i][j][0]
            dp[i+1][(j+d)%D][1] %= MOD

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

N = len(K)
dp = [[[0]*2 for _ in range(D)] for _ in range(N+1)] # 上から i まで見て余りが j であるものの数
dp[0][0][0] = 1

# 0 -> K ちょうど
# 1 -> K より小さい
for i in range(N):
    k = int(K[i])
    for j in range(D):
        dp[i+1][(j+k)%D][0] += dp[i][j][0]
        dp[i+1][(j+k)%D][0] %= MOD
        for d in range(10):
            dp[i+1][(j+d)%D][1] += dp[i][j][1]
            if d < k:
                dp[i+1][(j+d)%D][1] += dp[i][j][0]
            dp[i+1][(j+d)%D][1] %= MOD

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

Submission status: Accepted

Solution code:
mod=10**9+7
n=input()
D=int(input())
N=len(n)+1
dp=[[[0 for i in range(2)] for j in range(D)] for k in range(len(n)+1)]
dp[0][0][0]=1
for a in range(N-1):
  x=int(n[a])
  for b in range(D):
    for d in range(10):
      if d<x:
        dp[a+1][(b+d)%D][1]+=dp[a][b][0]+dp[a][b][1]
      elif d==x:
        dp[a+1][(b+d)%D][0]+=dp[a][b][0]
        dp[a+1][(b+d)%D][1]+=dp[a][b][1]
      else:
        dp[a+1][(b+d)%D][1]+=dp[a][b][1]
      dp[a+1][(b+d)%D][1]%=mod
      dp[a+1][(b+d)%D][0]%=mod
ans=sum(dp[-1][0])
print((ans-1)%mod)

Submission status: Accepted

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] = (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: Accepted

Solution code:
K=input()
N=len(K)
D=int(input())
import numpy as np
d=np.zeros((N+1,D),dtype=np.int64)
d2=np.zeros((N+1,D),dtype=np.int64)
d[0,0]=1
m=10**9+7
r=(D+9)//D
for i in range(N):
    dc=d[i]
    dc2=d2[i]
    for j in range(r):
        dc=np.concatenate((dc,d[i]))
        dc2=np.concatenate((dc2,d2[i]))
    dc,dc2=np.cumsum(dc),np.cumsum(dc2)
    x=int(K[i])
    d[i+1]=np.roll(d[i],x)
    d2[i+1]=(dc[r*D:]-dc[r*D-x:(r+1)*D-x]+dc2[r*D:]-dc2[r*D-10:(r+1)*D-10])%m
print((d[-1,0]+d2[-1,0]-1)%m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout
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')

def main():
	MOD = 10**9 + 7
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	dp = [[0 for __ in range(2)] for _ in range(d)]
	dp[0][1] = 1
	for i in range(len(x)):
		ndp = [[0 for __ in range(2)] for _ in range(d)]
		for digsum in range(d):
			for tight in range(2):
				for nd in range(x[i]+1 if tight else 10):
					ns = (digsum + nd) % d 
					ntight = 1 if tight and nd == x[i] else 0
					ndp[ns][ntight] += dp[digsum][tight]
					ndp[ns][ntight] %= MOD
		dp = ndp

	ans = (dp[0][0] + dp[0][1] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
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')

def main():
	MOD = 10**9 + 7
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	dp = [[0]*2 for _ in range(d)]
	dp[0][1] = 1
	for i in range(len(x)):
		ndp = [[0]*2 for _ in range(d)]
		for digsum in range(d):
			for tight in range(2):
				for nd in range(x[i]+1 if tight else 10):
					ns = (digsum + nd) % d 
					ntight = 1 if tight and nd == x[i] else 0
					ndp[ns][ntight] += dp[digsum][tight]
					ndp[ns][ntight] %= MOD
		dp = ndp

	ans = (dp[0][0] + dp[0][1] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
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')

def main():
	MOD = 10**9 + 7
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	dp = [[[0]*2 for j in range(d)] for i in range(len(x)+1)]
	dp[0][0][1] = 1
	for i in range(len(x)):
		for digsum in range(d):
			for tight in range(2):
				for dig in range(x[i]+1 if tight else 10):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

	ans = (dp[len(x)][0][0] + dp[len(x)][0][1] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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)

	dp = [[[0]*2 for j in range(d)] for i in range(len(x)+1)]
	dp[0][0][1] = 1
	for i in range(len(x)):
		for digsum in range(d):
			for tight in range(2):
				for dig in range(x[i]+1 if tight else 10):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

	ans = (dp[len(x)][0][0] + dp[len(x)][0][1] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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

for i in range(L):
    Ki = int(K[i])
    
    for j in range(2):
        for k in range(D):
            for d in range(10 if j else Ki+1):
                dp[i+1][j|(d<Ki)][(k+d)%D] += dp[i][j][k]
                dp[i+1][j|(d<Ki)][(k+d)%D] %= MOD

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    k=input()
    len_k=len(k)
    d=int(input())
    mod=10**9+7
    dp_0=[[0]*d for _ in range(len_k+1)]
    dp_1=[[0]*d for _ in range(len_k+1)] 
    dp_0[0][0]=1
    for i in range(len_k):
        ni=int(k[i])
        for j in range(d):
            for dig in range(10):
                dp_1[i+1][(j+dig)%d]=(dp_1[i+1][(j+dig)%d]+dp_1[i][j])%mod
            for dig in range(ni):
                dp_1[i+1][(j+dig)%d]=(dp_1[i+1][(j+dig)%d]+dp_0[i][j])%mod
            dp_0[i+1][(j+ni)%d]=(dp_0[i+1][(j+ni)%d]+dp_0[i][j])%mod
    print((dp_0[len_k][0]+dp_1[len_k][0]-1)%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
k = input()
D = int(input())
mod = 10 ** 9 + 7
keta = len(k)
dp = [[[0] * (2) for _ in range(D)] for _ in range(keta + 1)]
# dp[keta][D][smaler]
dp[0][0][0] = 1
for i in range(keta):
    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[keta][0][1] + dp[keta][0][0] - 1)%mod)

Submission status: Accepted

Solution code:


def submit():
    k = input()
    lenk = len(k)
    d = int(input())
    f = lambda x: x % d
    modp = 10 ** 9 + 7

    dp = [[[0 for _ in range(d)],
           [0 for _ in range(d)]] for _ in range(lenk)]

    curr = int(k[0])
    for j in range(10):
        if j < curr:
            dp[0][0][f(j)] += 1
        if j == curr:
            dp[0][1][f(j)] += 1
            break

    for i in range(1, lenk):
        curr = int(k[i])
        for s in range(d):
            # smaller at prev
            for j in range(10):
                dp[i][0][f(s + j)] += dp[i - 1][0][s]
                dp[i][0][f(s + j)] %= modp
            
            # unsmall at prev
            for j in range(curr + 1):
                dp[i][j == curr][f(s + j)] += dp[i - 1][1][s]
                dp[i][j == curr][f(s + j)] %= modp
                
    ans = dp[lenk - 1][0][0] + dp[lenk - 1][1][0] - 1
    print(ans % modp)

submit()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

k = ni()
s = str(k)
n = len(s)
d = ni()

dp = [[[0] * 2 for _ in range(d + 1)] 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):
            dmax = 9 if k else int(s[i])
            for D in range(dmax + 1):
                ni = i + 1
                nj = (j + D) % d
                nk = k | (D < dmax)
                dp[ni][nj][nk] += dp[i][j][k]
                dp[ni][nj][nk] %= mod

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    k = input()
    modulo = int(input())
    dp = [[0] * 2 for _ in range(modulo)]
    dp[0][0] = 1

    for d in k:
        d = int(d)
        ndp = [[0] * 2 for _ in range(modulo)]
        for r, lt in product(range(modulo), range(2)):
            for x in range(10):
                if (not lt) and x > d:
                    continue
                nlt = max(lt, x < d)
                nr = (r + x) % modulo
                ndp[nr][nlt] += dp[r][lt]
                if ndp[nr][nlt] >= MOD:
                    ndp[nr][nlt] -= MOD
        dp = ndp

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7

def main():
    K = input()
    D = int(input())

    dp = [[[0]*2 for _ in range(D)] for _ in range(len(K) + 1)] 
    dp[0][0][0] = 1
    for i in range(len(K)):
        M = int(K[i])
        for j in range(D):
            for k in range(10):
                if k < M:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1] + dp[i][j][0]
                elif k == M:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1]
                    dp[i + 1][(j + k)%D][0] += dp[i][j][0]
                else:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1]
                dp[i + 1][(j + k)%D][0] %= MOD
                dp[i + 1][(j + k)%D][1] %= MOD
    ans = sum(dp[-1][0])
    print((ans - 1)%MOD)       
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
n = len(s)
d = int(input())
dp = [[[0,0] for _ in range(d)] for _ in range(n+1)]
mod = 10**9 + 7
dp[0][0][1] = 1

for i in range(n):
    for j in range(d):
        for k in range(10):
            dp[i+1][(j+k)%d][0] += dp[i][j][0]
            dp[i+1][(j+k)%d][0] %= mod
        for k in range(int(s[i])):
            dp[i+1][(j+k)%d][0] += dp[i][j][1]
            dp[i+1][(j+k)%d][0] %= mod
        dp[i+1][(j+int(s[i]))%d][1] += dp[i][j][1]
print((sum(dp[n][0])-1)%mod)

Submission status: Accepted

Solution code:
#intじゃ無理
K=str(input())
D=int(input())
N=len(K)
P=10**9+7


#DP[i][smaller][j]=上からi(1<=i<=len(K))桁目までで桁総和modDがj(0<=j<=D-1)の個数
DP=[[[0]*(D) for index1 in range(2)] for index2 in range(N+1)]
#i=0に関しては初期値として与える
DP[0][0][0]=1

#桁DP:O(ND)
for i in range(1,N+1):
    for j in range(D):
        for k in range(10):
            DP[i][1][(j+k)%D]=(DP[i][1][(j+k)%D]+DP[i-1][1][j])%P
        for l in range(int(K[i-1])):
            DP[i][1][(j+l)%D]=(DP[i][1][(j+l)%D]+DP[i-1][0][j])%P
        DP[i][0][(j+int(K[i-1]))%D]=(DP[i][0][(j+int(K[i-1]))%D]+DP[i-1][0][j])%P

#0を除く
print((DP[N][0][0]+DP[N][1][0]-1)%P)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    # TDPC E or EDPC S
    S = [s for s in input()]
    N = len(S)
    D = int(input())
    dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
    dp[0][0][0] = 1
    from itertools import product
    for i, smaller, dsum in product(range(N), range(2), range(D)):
        lim = 9 if smaller else int(S[i])
        for d in range(lim+1):
            dp[i+1][smaller or d < lim][(dsum+d) % D] += dp[i][smaller][dsum]
            dp[i+1][smaller or d < lim][(dsum+d) % D] %= MOD
    print((dp[N][0][0] + dp[N][1][0] - 1) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    # TDPC E or EDPC S
    S = [s for s in input()]
    N = len(S)
    D = int(input())
    dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
    dp[0][0][0] = 1
    from itertools import product
    for i, smaller, dsum in product(range(N), [True, False], range(D)):
        lim = 9 if smaller else int(S[i])
        for d in range(lim+1):
            dp[i+1][smaller or d < lim][(dsum+d) % D] += dp[i][smaller][dsum]
            dp[i+1][smaller or d < lim][(dsum+d) % D] %= MOD
    print((dp[N][0][0] + dp[N][1][0] - 1) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    # TDPC E or EDPC S
    S = input()
    N = len(S)
    D = int(input())
    dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
    dp[0][0][0] = 1
    from itertools import product
    for i, smaller, dsum in product(range(N), [True, False], range(D)):
        lim = 9 if smaller else int(S[i])
        for d in range(lim+1):
            dp[i+1][smaller or d < lim][(dsum+d) % D] += dp[i][smaller][dsum]
            dp[i+1][smaller or d < lim][(dsum+d) % D] %= MOD
    print((dp[N][0][0] + dp[N][1][0] - 1) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = [int(n) for n in list(input())]
d = int(input())
p = 10**9+7
DP = [[0]*d, [0]*d]
DP[1][0] = 1
for n in N:
    DP_ = [[0]*d, [0]*d]
    for i in range(2):
        for j in range(d):
            for k in range(n+i):
                DP_[i][j] += DP[1][(j-k) % d] % p
            for k in range(n+i, 10):
                DP_[i][j] += DP[0][(j-k) % d] % p
            DP_[i][j] %= p
    DP = DP_
print((DP[1][0] + p - 1) % p)

Submission status: Accepted

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=list(input())
    D=I()
    N=len(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
            
    #推移
    now=0#tが0ではない位置
    
    for i in range(N):
        num=(int(K[i]))
        #t
        dpt[i+1][(now+num)%D]=1
        for k in range(num):
            dpl[i+1][(now+k)%D]+=1
        now=(now+num)%D
                    
        
        #l，尺取り
        S=0
        for j in range(10):#初期化，0~9までの和
            S+=dpl[i][j%D]
            
        for j in range(D):#あまりが10~D-1,0~9の順に配る
            dpl[i+1][(j+9)%D]+=S
            dpl[i+1][(j+9)%D]%=mod
            S+=dpl[i][(j+10)%D]-dpl[i][j%D]
        
                
    #0もカウントしているmので1ひく
    print((dpt[-1][0]+dpl[-1][0]-1)%mod)
    
    
            
    
    

main()

Submission status: Accepted

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
            
    #推移
    now=0#tが0ではない位置
    
    for i in range(N):
        num=(int(K[i]))
        #t
        dpt[i+1][(now+num)%D]=1
        for k in range(num):
            dpl[i+1][(now+k)%D]+=1
        now=(now+num)%D
                    
        
        #l，尺取り
        S=0
        for j in range(10):#初期化，0~9までの和
            S+=dpl[i][j%D]
            
        for j in range(D):#あまりが10~D-1,0~9の順に配る
            dpl[i+1][(j+9)%D]+=S
            dpl[i+1][(j+9)%D]%=mod
            S+=dpl[i][(j+10)%D]-dpl[i][j%D]
        
                
    #0もカウントしているmので1ひく
    print((dpt[-1][0]+dpl[-1][0]-1)%mod)
    
    
            
    
    

main()

Submission status: Accepted

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]:
        lim = 9 if smaller_flg else int(str(K)[digit])
        for digit_num in range(lim+1):
            new_smaller_flg = smaller_flg or digit_num < lim
            for mod_d in range(D):
                new_mod_d = (mod_d + digit_num)%D
                dp[digit+1][new_smaller_flg][new_mod_d] += dp[digit][smaller_flg][mod_d]
                dp[digit+1][new_smaller_flg][new_mod_d] %= MOD

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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]:
        lim = 9 if smaller_flg else int(str(K)[digit])
        for digit_num in range(lim+1):
            new_smaller_flg = smaller_flg or digit_num < lim
            for mod_d in range(D):
                new_mod_d = (mod_d + digit_num)%D
                dp[digit+1][new_smaller_flg][new_mod_d] += dp[digit][smaller_flg][mod_d]
                dp[digit+1][new_smaller_flg][new_mod_d] %= MOD

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

Submission status: Accepted

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

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

dp[N][0][0]=1
dp[N][0][1]=1

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

        dp[i][j][0]=ans%mod

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

        ans+=dp[i+1][(j+int(K[i]))%D][1]

        dp[i][j][1]=ans%mod

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

Submission status: Accepted

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)

Submission status: Accepted

Solution code:
k = input()
d = int(input())

mod = 10 ** 9 + 7

dp = [[0] * d for _ in range(2)]
dp[1][0] = 1

for i in k:
    i = int(i)
    dp2 = [[0] * d for _ in range(2)]

    for j in range(d):
        dp2[1][(j + i) % d] += dp[1][j]

    for j in range(d):
        for k in range(i):
            dp2[0][(j + k) % d] += dp[1][j]

    for j in range(d):
        for k in range(10):
            dp2[0][(j + k) % d] += dp[0][j]

    dp = [[j % mod for j in k] for k in dp2]

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