Submission #3421479
Source Code Expand
D = int(input()) N = input() L = len(N) 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 in range(L): for less in range(2): lim = 9 if less else int(N[i]) 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][1][0] - 1)
Submission Info
Submission Time | |
---|---|
Task | E - 数 |
User | prd_xxx |
Language | PyPy3 (2.4.0) |
Score | 4 |
Code Size | 449 Byte |
Status | AC |
Exec Time | 981 ms |
Memory | 61404 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 4 / 4 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 209 ms | 41712 KB |
01 | AC | 695 ms | 55388 KB |
02 | AC | 981 ms | 61404 KB |
90 | AC | 173 ms | 38256 KB |
91 | AC | 183 ms | 39024 KB |