Submission #11376221
Source Code Expand
#define _USE_MATH_DEFINES #include <iostream> #include <string> #include <utility> #include <stack> #include <vector> #include <queue> #include <algorithm> #include <map> #include <climits> #include <set> #include <cmath> #include <numeric> #include <iomanip> #include <cassert> using namespace std; const long long MOD = 1000000007; long long dp[10000][100]; int main(){ int D; cin >> D; string N; cin >> N; int cur_digit = (int) (N[0] - '0'); for(int i = 0; i < cur_digit; i++){ dp[0][i % D] ++; } long long tmp_mod = cur_digit % D; for(int i = 0; i < N.size() - 1; i++){ for(int j = 0; j < D; j++){ for(int k = 0; k < 10; k++){ dp[i + 1][(j + k) % D] = (dp[i + 1][(j + k) % D] + dp[i][j]) % MOD; } } cur_digit = (int) (N[i + 1] - '0'); for(int j = 0; j < cur_digit; j++){ dp[i + 1][(tmp_mod + j) % D] = (dp[i + 1][(tmp_mod + j) % D] + 1) % MOD; } tmp_mod = (tmp_mod + cur_digit) % D; } dp[N.size() - 1][tmp_mod] = (dp[N.size() - 1][tmp_mod] + 1) % MOD; dp[N.size() - 1][0] = (dp[N.size() - 1][0] - 1 + MOD) % MOD; cout << dp[N.size() - 1][0] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 数 |
User | katom |
Language | C++14 (GCC 5.4.1) |
Score | 4 |
Code Size | 1295 Byte |
Status | AC |
Exec Time | 48 ms |
Memory | 8064 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 | 2 ms | 256 KB |
01 | AC | 31 ms | 8064 KB |
02 | AC | 48 ms | 7936 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |