Submission #5896533
Source Code Expand
#include <cstdio> #include <iostream> #include <string> using namespace std; using ll = long long; const ll MM = 1000000007; string N; int D; ll num[10000][10][101] = {}; int mod(int a, int b){ if (a<0) { int c = int(double(-a)/double(b)) + 1; return (a + b * c) % b; } else return a % b; } void solve(int kk) { for (int k = 1; k < kk; ++k) { for (int j = 0; j < D; ++j) { num[k][0][j] = num[k-1][9][j]; } for (int i = 1; i < 10; ++i) { for (int j = 0; j < D; ++j) { int a = mod(j-i, D); int f = i%D == j ? 1 : 0; num[k][i][j] = (num[k-1][9][a] + num[k][i-1][j] + f) % MM; } } } } int main(int argc, char *argv[]) { cin >> D; cin >> N; if (D==1) { cout << N << endl; return 0; } for (int i = 0; i < 10; ++i) { for (int j = 1; j < i+1; ++j) { num[0][i][j % D] += 1; } } solve(N.size()); int c = N[0] - '0'; int a=mod(D-c, D); ll ans = num[N.size()-1][c-1][0]; // printf("\n%d\n", ans); for (int i = 1; i < N.size(); ++i) { c = N[i] - '0'; int sub = 0; if (c > 0) { sub = num[N.size() - i - 1][c-1][a]; } if(a == 0) { // xxx000もOk sub += 1; } if (i == N.size()-1 && a+c % D == 0) sub+=1; ans = (ans + sub) % MM; // printf("c=%d, a=%d, sub=%d", c, a, sub); a = mod(a-c, D); // printf(" newa=%d\n", a); } printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 数 |
User | vintersnow |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1684 Byte |
Status | WA |
Exec Time | 65 ms |
Memory | 79232 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 4 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 2 ms | 1024 KB |
01 | WA | 47 ms | 79232 KB |
02 | WA | 65 ms | 78208 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 512 KB |