Submission #2742441


Source Code Expand

from functools import reduce
from collections import defaultdict

k = int(input())
n = input()
m = 1000000007

def f(dd, x):
    y = int(x)
    dd2 = defaultdict(int)
    for less, modk in dd:
        maxd = 9 if less else y
        for d in range(maxd+1):
            less_ = less or d < y
            modk_ = (modk + d) % k
            dd2[less_, modk_] += dd[less, modk]
            dd2[less_, modk_] %= m
    return dd2

dd = reduce(f, n, {(False, 0):1})
print(dd[True, 0] + dd[False, 0] - 1)

Submission Info

Submission Time
Task E - 数
User zehnpaard
Language Python (3.4.3)
Score 0
Code Size 516 Byte
Status TLE
Exec Time 2104 ms
Memory 3572 KB

Judge Result

Set Name All
Score / Max Score 0 / 4
Status
AC × 3
TLE × 2
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 81 ms 3572 KB
01 TLE 2103 ms 3572 KB
02 TLE 2104 ms 3572 KB
90 AC 23 ms 3572 KB
91 AC 24 ms 3572 KB