Problem:


Score : 100 points

Problem Statement

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

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

Constraints

All values in input are integers.

1 \leq K < 10^{10000}

1 \leq D \leq 100

Input

Input is given from Standard Input in the following format:

K
D

Output

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

Sample Input 1

30
4

Sample Output 1

6

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

Sample Input 2

1000000009
1

Sample Output 2

2

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

Sample Input 3

98765432109876543210
58

Sample Output 3

635270834



Sample input:
30
4


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

memo = [[[[-1 for l in range(2)] for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flagX, flagY): #flagX upper bound, flagY lower bound
    if digit == -1:
        if flagY and current_sum % D == 0:
            return 1
        else:
            return 0

    if memo[digit][current_sum][flagX][flagY] != -1:
        return memo[digit][current_sum][flagX][flagY]

    ret = 0
    for i in range(10):
        if flagX:
            ret += f(digit-1, (current_sum+i)%D, flagX, flagY or (1 if i >= 1 else 0))
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0, flagY or (1 if i >= 1 else 0))
        elif i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1, flagY or (1 if i >= 1 else 0))
            
    memo[digit][current_sum][flagX][flagY] = ret % MOD
    return ret

print(f(N-1, 0, 0, 0) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from numpy.fft import rfft, irfft
MOD = 10 ** 9 + 7
K = [int(x) for x in input().rstrip()]
L = len(K)
D = int(input())

fft_len = 1
while fft_len < 2*D:
    fft_len *= 2

def fft_convolve(A,B):
    return np.round(irfft(rfft(A,fft_len) * rfft(B,fft_len))).astype(np.int64) % MOD

def convolve(A,B):
    M = 1 << 16
    mask = M - 1
    A1,A2 = A>>16, A&mask
    B1,B2 = B>>16, B&mask
    X,Y,Z = [fft_convolve(P,Q) for P,Q in [[A1,B1],[A1-A2,B1-B2],[A2,B2]]]
    X = (X << 32) + ((X-Y+Z) << 16) + Z
    X[:D] += X[D:D+D]
    return X[:D] % MOD

# d桁以下、自由に使った場合の余りごとの個数。0を含めて数えておく
ones = [np.zeros(D,dtype=np.int64)]
for x in range(10):
    arr = ones[-1].copy()
    arr[x%D] += 1
    ones.append(arr)
full = []
dp = np.zeros(D, dtype=np.int64)
dp[0] = 1
full.append(dp)
for d in range(1,L):
    dp = convolve(dp,ones[10])
    full.append(dp)

dist = np.zeros(D+D, dtype=np.int64)

cumsum = 0
for i,x in enumerate(K):
    arr = convolve(ones[x], full[L-i-1])
    dist[cumsum:cumsum+D] += arr
    cumsum += x
    cumsum %= D
dist[cumsum] += 1 # 全部そのまま使う

answer = dist[::D].sum() - 1 # 0除外
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

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

allDP = [[0 for _ in range(D)] for _ in range(len(listN) + 1)]  # allDP[digit][sum]
lessNDP = [[0 for _ in range(D)] for _ in range(len(listN) + 1)]  # lessNDP[digit][sum]

allDP[0][0] = 1
lessNDP[0][0] = 1

for digit in range(1, len(listN) + 1) :
    for d in range(D) :
        for i in range(10) :
            allDP[digit][d] = (allDP[digit][d] + allDP[digit - 1][(d - i) % D]) % MOD
            if listN[-digit] == i :  # digit番目がちょうどであるからdigit-1桁目がN以下
                lessNDP[digit][d] = (lessNDP[digit][d] + lessNDP[digit - 1][(d - i) % D]) % MOD
            elif listN[-digit] > i :  # digit番目がNより少ないのでdigit-1桁以下はすべて動く
                lessNDP[digit][d] = (lessNDP[digit][d] + allDP[digit - 1][(d - i) % D]) % MOD

ans = (lessNDP[len(listN)][0] - 1) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
M = 10**9+7
K = input()
D = int(input())
N = len(K)
dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]
dp[0][0][0] = 1
for dgt in range(N):
    for d in range(D):
        for is_less in range(2):
            c = int(K[dgt])
            for nxt in range(10):
                if nxt < c:
                    dp[dgt+1][(d+nxt)%D][1] += dp[dgt][d][is_less]
                elif nxt == c:
                    dp[dgt+1][(d+nxt)%D][is_less] += dp[dgt][d][is_less]
                elif is_less:
                    dp[dgt+1][(d+nxt)%D][is_less] += dp[dgt][d][is_less]
                    
print((dp[N][0][0]+dp[N][0][1]-1) % M)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

M = 10**9 + 7
K = int(input())
D = int(input())

dp = [[None] * 100 for _ in range(10**5 + 1)]
def f(k, i):
    if dp[i][k] is not None:
        return dp[i][k]

    if i == 0:
        r = (k % D) == 0
        dp[i][k] = r
        return r
    r = sum(f((k + x) % D, i - 1) for x in range(0, 10)) % M
    dp[i][k] = r
    return r

# dp = [[0] * 100 for _ in range(10**5 + 1)]
# for i in range(10**5 + 1):
#     for k in range(100):
#         if i == 0:
#             dp[i][k] = int((k % D) == 0)
#         else:
#             dp[i][k] = sum(dp[(k + x) % D][i - 1] for x in range(0, 10)) % M
#
# def f(k, i):
#     return dp[i][k]

sk = str(K)
dig = len(sk)
answer = 0
s = sum(map(int, list(sk)))
for j in range(int(sk[-1]) + 1):
    if (s - j) % D == 0:
        answer += 1
        answer %= M

if dig > 1:
    s -= int(sk[-1])
    for i in range(dig - 1, 1, -1):
        if sk[i - 1] == "0":
            continue
        for j in range(int(sk[i - 1])):
            answer += f((s - 1) % D - j, dig - i) % M
        s -= int(sk[i - 1])

    for k in range(1, int(sk[0])):
        answer += f(k % D, dig - 1) % M

    if dig > 1: # 先頭0固定
        for k in range(10):
            answer += f(k % D, dig - 2) % M


print((answer - 1) % M)

Submission status: Time Limit Exceeded

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)]
dp[0][0][0] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

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

        for ndk in ndp:
            ndk %= md

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int,list(input())))
d = int(input())
f(ks, d)

Submission status: Time Limit Exceeded

Solution code:
def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        k = int(k)
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

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

        for ndk in ndp:
            ndk %= md

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = input()
d = int(input())
f(ks, d)

Submission status: Time Limit Exceeded

Solution code:
def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        k = int(k)
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

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

        for dk in dp:
            dk %= md

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = input()
d = int(input())
f(ks, d)

Submission status: Time Limit Exceeded

Solution code:
md = 10 ** 9 + 7
ks = input()
d = int(input())
dp = [0] * d
just = 0

for k in ks:
    k = int(k)
    ndp = [0] * d

    for di, dk in enumerate(dp):
        for ndi in range(di, di + 10):
            ndp[ndi % d] += dk

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

    for dk in dp:
        dk %= md

    just = (just + k) % d
    dp = ndp

print((dp[0] + (just == 0) - 1) % md)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def cnt(i, f, s):
    if i == n:
        if s % d or s == 0:
            return 0
        else:
            return 1
    t = (i, f, s)
    if t in memo:
        return memo[t]
    if f:
        m = 10
        re = 0
    else:
        ki = int(k[i])
        m = ki
        re = cnt(i + 1, 0, s + ki)
    for j in range(m):
        re += cnt(i + 1, 1, s + j)
    memo[t] = re = re % md
    return re


md = 10 ** 9 + 7
memo = {}
k = input()
d = int(input())
n = len(k)
print(cnt(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    dl = list(range(D)) * (10 // D + 2)
    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = dl[d + k]
            dpi1j[d_] += dpij[d]
            dpi1j[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100
print(f2(K, D))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = (d + k) % D
            dpi1j[d_] += dpij[d]
            if dpi1j[d_] > mod:
                dpi1j[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100
print(f2(K, D))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = (d + k) % D
            dpi1j[d_] += dpij[d]
            dpi1j[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f2(K, D))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            dpi1 = dp[i + 1]
            for d in range(D):
                for k in range(uki + 1):
                    dpi1j_ = dpi1[j or k < ki]
                    d_ = (d + k) % D
                    dpi1j_[d_] += dpij[d]
                    if dpi1j_[d_] > mod:
                        dpi1j_[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    if dpij_[d_] > mod:
                      dpij_[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Submission status: Time Limit Exceeded

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

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

for i in range(len(k)):
    for j in range(2):
        for m in range(d):
            if j == 1:
                for num in range(10):
                    dp[i+1][j][(m+num)%d] += dp[i][j][m]
                    dp[i+1][j][(m+num)%d] %= mod
            else:
                for num in range(int(k[i])+1):
                    if num != int(k[i]):
                        dp[i+1][1][(m+num)%d] += dp[i][j][m]
                        dp[i+1][1][(m+num)%d] %= mod
                    else:
                        dp[i+1][0][(m+num)%d] += dp[i][j][m]
                        dp[i + 1][0][(m + num) % d] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

s=list(map(int,input()))
d=int(input())
n=len(s)
mod=10**9+7
memo=[[[-1 for i in range(d)]for i in range(2)]for i in range(n+1)]
def dgtdp(k,t,md):
    if memo[k][t][md]!=-1:
        return memo[k][t][md]
    if k>=n:
        return md==0
    x=s[k]
    lim= x if t else 9
    ret=0
    for i in range(lim+1):
        ret+=dgtdp(k+1,t and (i==lim),(md+i)%d)
        ret%=mod
    memo[k][t][md]=ret
    return ret

print((dgtdp(0,True,0)-1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

s=list(map(int,input()))
d=int(input())
mod=10**9+7
memo=[[[-1 for i in range(d)]for i in range(2)]for i in range(len(s)+1)]
def dgtdp(k,t,md):
    if memo[k][t][md]!=-1:
        return memo[k][t][md]
    if k==len(s):
        return md==0
    x=s[k]
    lim= x if t else 9
    ret=0
    for i in range(lim+1):
        ret+=dgtdp(k+1,t and (i==lim),(md+i)%d)
        ret%=mod
    memo[k][t][md]=ret
    return ret

print((dgtdp(0,True,0)-1)%mod)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:


MOD = 1000000007

def F(k, s):
    return dp[k][s]

def solve(n):
    resp = 0
    n = map(int, str(n))
    pref = 0
    for i in range(len(n)):
        for d in range(n[i]):
            resp += F(len(n) - i - 1, (pref - d) % D)
        pref -= n[i]
        pref %= D
    return resp


K = raw_input()
D = input()

# dp[i][j] = cant de numeros de i digitos con suma % d = j
dp = [[0] * D for _ in range(len(K) + 1)]
dp[0][0] = 1
for i in range(1, len(K) + 1):
    for j in range(D):
        for d in range(10):
            dp[i][j] += dp[i - 1][(j - d) % D]

resp = solve(K) - 1
if sum(map(int, str(K))) % D == 0:
    resp += 1
print(resp % MOD)

Submission status: Time Limit Exceeded

Solution code:
K = list(map(int, input()))
D = int(input())

mod = 10 ** 9 + 7

next_dp = [0] * D
border = 0

for current_digit in K:
    dp, next_dp = next_dp, [0] * D

    for current_mod, cnt in enumerate(dp):
        for next_mod in range(current_mod, current_mod + 10):
            next_dp[next_mod % D] += cnt

    for next_mod in range(border, current_digit + border):
        next_dp[next_mod % D] += 1

    border = (border + current_digit) % D

    for i in range(D):
        next_dp[i] %= mod

print((next_dp[0] + (border == 0) - 1) % mod)

Submission status: Time Limit Exceeded

Solution code:
K = list(map(int, input()))
D = int(input())

mod = 10 ** 9 + 7

next_dp = [0] * D
border = 0

for current_digit in K:
    dp, next_dp = next_dp, [0] * D
    for current_mod, cnt in enumerate(dp):
        for next_mod in range(current_mod, current_mod + 10):
            next_dp[next_mod % D] += cnt

    for next_mod in range(border, current_digit + border):
        next_dp[next_mod % D] += 1

    border = (border + current_digit) % D

    for i in range(D):
        next_dp[i] %= mod
print((next_dp[0] + (border == 0) - 1) % mod)

Submission status: Time Limit Exceeded

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

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

for i in range(length):
    for j in range(2):
        for k in range(D):
            if j == 1:
                x = 9
            else:
                x = int(K[i])
            for d in range(x + 1):
                dp[i + 1][j or d < x][(k + d) % D] += dp[i][j][k]
                dp[i + 1][j or d < x][(k + d) % D] %= mod
ans = 0
for i in range(2):
    ans += dp[length][i][0]

print((ans - 1) % mod)

Submission status: Time Limit Exceeded

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

L=len(K)

DP=[0]*D#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数
LIMIT=[]

for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        LIMIT=j%D
    else:
        DP[j%D]+=1

for ketanum in K[1:]:
    NDP=[0]*D

    for i in range(D):
        for j in range(10):
            NDP[(i+j)%D]=(NDP[(i+j)%D]+DP[i])%mod

    for j in range(int(ketanum)):
        NDP[(LIMIT+j)%D]+=1

    LIMIT=(LIMIT+int(ketanum))%D

    DP=NDP

print((DP[0]-1+ (LIMIT==0) )%mod)

Submission status: Time Limit Exceeded

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

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]+=1
    else:
        DP[0][j%D]+=1

for ketanum in K[1:]:
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[0][i])%mod

            if j>int(ketanum):
                continue
            if j==int(ketanum):
                NDP[1][(i+j)%D]=(NDP[1][(i+j)%D]+DP[1][i])%mod
            else:
                NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[1][i])%mod

    DP=NDP

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

Submission status: Time Limit Exceeded

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

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]+=1
    else:
        DP[0][j%D]+=1
        


for keta in range(1,L):
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]+=DP[0][i]

    for i in range(D):
        for j in range(10):
            if j>int(K[keta]):
                continue
            if j==int(K[keta]):
                NDP[1][(i+j)%D]+=DP[1][i]
            else:
                NDP[0][(i+j)%D]+=DP[1][i]

    DP=NDP

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

Submission status: Time Limit Exceeded

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

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]+=1
    else:
        DP[0][j%D]+=1

for keta in range(1,L):
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[0][i])%mod

    for i in range(D):
        for j in range(10):
            if j>int(K[keta]):
                continue
            if j==int(K[keta]):
                NDP[1][(i+j)%D]=(NDP[1][(i+j)%D]+DP[1][i])%mod
            else:
                NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[1][i])%mod

    DP=NDP

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

Submission status: Time Limit Exceeded

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

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

Submission status: Accepted

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

S = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
N = len(S)

dp = [[[0] * D for j in range(2)] for i in range(N)]
# dp[i][smaller][d]

x0 = S[0]
dp[0][0][int(x0) % D] = 1
for i in range(int(x0)):
  dp[0][1][i % D] += 1

last = int(x0) % D
for i in range(1, len(S)):
  x = S[i]
  dp[i][0][(last + int(x)) % D] += dp[i - 1][0][last]
  dp[i][0][(last + int(x)) % D] %= DIV
  
  for j in range(int(x)):
    dp[i][1][(last + j) % D] += dp[i - 1][0][last]
    dp[i][1][(last + j) % D] %= DIV
  
  for j in range(D):
    for k in range(10):
      dp[i][1][(j + k) % D] += dp[i - 1][1][j]
      dp[i][1][(j + k) % D] %= DIV
  last = (last + int(x)) % D
    
print((dp[-1][0][0] + dp[-1][1][0] - 1) % DIV)

Submission status: Accepted

Solution code:
n = input()
d = int(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: Accepted

Solution code:
# S - Digit Sum
k = input()
d = int(input())
n = len(k)
MOD = 10**9+7

# dp[i][j][l]
# i桁目までみたとき、
# j=0:k未満であることが確定していない。j=1:k未満であることが確定している。
# l:桁和のmod dがlである数の個数。

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

for i in range(n):
  for j in range(d):
    # k未満であることが確定していれば、i桁目は0～9の数字がとれる。
    for l in range(10):
      dp[i+1][1][(j+l)%d] += dp[i][1][j]
      dp[i+1][1][(j+l)%d] %= MOD
    # k未満であることが確定していない場合、i桁目を0～k[i]-1にすればk未満であることが確定する。
    for l in range(int(k[i])):
      dp[i+1][1][(j+l)%d] += dp[i][0][j]
      dp[i+1][1][(j+l)%d] %= MOD
    # k未満であることが確定していない場合、i桁目をk[i]にすればk未満であることは確定しない。
    dp[i+1][0][(j+int(k[i]))%d] += dp[i][0][j]
    dp[i+1][0][(j+int(k[i]))%d] %= MOD
# 0が解答にカウントされているので、0の分を除くため-1する。
print((dp[n][0][0]+dp[n][1][0]-1)%MOD)
# print(dp)

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


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(K[i]):
            #     # 1~K[i]-1をつけるとぴったりにならないグループへ行く
            #     dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]
            # 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(10):
                m = (k + l) % D
                if l < K[i]:
                    dp[i + 1, 0, m] += dp[i, 0, k] + dp[i, 1, k]
                else:
                    dp[i + 1, 0, m] += dp[i, 0, k]  # 1~9を考慮可能
                dp[i + 1, 0, m] %= 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(K[i]):
                # 1~K[i]-1をつけるとぴったりにならないグループへ行く
                dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]
            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
            # ぴったりグループ
            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~K[i]-1をつけるとぴったりにならないグループへ行く
                dp[i + 1, 0, (k + l) % D] %= MOD
            # ぴったりグループ
            if dp[i, 1, k]:
                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)