Submission #5549562
Source Code Expand
#include <iostream> #include <string> #include <utility> #include <algorithm> #include <map> #include <set> #include <vector> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <iomanip> using namespace std; #define REP(i, n) for(ll i = 0;i < n;i++) #define REPR(i, n) for(ll i = n;i >= 0;i--) #define FOR(i, m, n) for(ll i = m;i < n;i++) #define FORR(i, m, n) for(ll i = m;i >= n;i--) #define REPO(i, n) for(ll i = 1;i <= n;i++) #define ll long long #define INF (ll)1 << 60 #define MINF (-1 * INF) #define ALL(n) n.begin(),n.end() #define MOD (ll)1000000007 #define P pair<ll, ll> ll d, dp[11000][2][110]; string s; int main() { dp[0][0][0] = 1; cin >> d >> s; REP(i, s.size()) { ll now = s[i] - '0'; REP(sm, 2) { REP(j, d) { for (ll k = 0; k <= (sm ? 9 : now); k++) { dp[i + 1][sm or k < now][(j + k) % d] += dp[i][sm][j]; dp[i + 1][sm or k < now][(j + k) % d] %= MOD; } } } } cout << dp[s.size()][0][0] + dp[s.size()][1][0] - 1 << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - 数 |
User | kenken714 |
Language | C++14 (GCC 5.4.1) |
Score | 4 |
Code Size | 1053 Byte |
Status | AC |
Exec Time | 183 ms |
Memory | 18688 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 | 3 ms | 384 KB |
01 | AC | 112 ms | 18688 KB |
02 | AC | 183 ms | 18688 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |