Submission #3974108

Source Code Expand

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

S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[(d+v)%D][1] += w0
        T[(d+c)%D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[(d+v)%D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)

Submission Info

Submission Time
Task S - Digit Sum
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 485 Byte
Status AC
Exec Time 725 ms
Memory 45020 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 25
Set Name Test Cases
All 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21
Case Name Status Exec Time Memory
0_00 AC 162 ms 38256 KiB
0_01 AC 166 ms 38384 KiB
0_02 AC 178 ms 40048 KiB
1_00 AC 164 ms 38256 KiB
1_01 AC 167 ms 38256 KiB
1_02 AC 200 ms 42092 KiB
1_03 AC 725 ms 42716 KiB
1_04 AC 615 ms 43740 KiB
1_05 AC 559 ms 43100 KiB
1_06 AC 574 ms 43356 KiB
1_07 AC 558 ms 43100 KiB
1_08 AC 623 ms 43356 KiB
1_09 AC 649 ms 43356 KiB
1_10 AC 631 ms 43356 KiB
1_11 AC 583 ms 43228 KiB
1_12 AC 577 ms 43228 KiB
1_13 AC 615 ms 45020 KiB
1_14 AC 625 ms 43740 KiB
1_15 AC 617 ms 43356 KiB
1_16 AC 595 ms 43228 KiB
1_17 AC 629 ms 44252 KiB
1_18 AC 543 ms 42972 KiB
1_19 AC 559 ms 43100 KiB
1_20 AC 163 ms 38256 KiB
1_21 AC 163 ms 38256 KiB