Submission #5418760
Source Code Expand
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <stack> #include <queue> #include <cmath> #include <tuple> #include <cstdio> #include <bitset> #include <sstream> #include <iterator> #include <numeric> #include <map> #include <cstring> #include <set> using namespace std; #define DEBUG_ //!!提出時にコメントアウト!! #ifdef DEBUG_ #define dump(x) cerr << #x << " = " << (x) << endl; #else #define dump(x) ; //何もしない文 #endif #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換 #define pb push_back #define eb emplace_back //#define int long long typedef long long LL; typedef vector<int> VI; typedef vector<LL> VL; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> std::string printVector(const std::vector<T> &data) { std::stringstream ss; std::ostream_iterator<T> out_it(ss, ", "); ss << "["; std::copy(data.begin(), data.end() - 1, out_it); ss << data.back() << "]"; return ss.str(); } const int MOD = 1e9+7; const LL LINF = 1001002003004005006ll; const int INF = 1001001001; LL dp[10005][105][2]; signed main(int argc, char const *argv[]) { cin.tie(0); ios::sync_with_stdio(false); int D; cin >> D; string N; cin >> N; memset(dp,0,sizeof(dp)); dp[0][0][0] = 1; for(int pos = 0; pos < int(N.length()); pos++){ for(int sum = 0; sum < D; sum++){ for(int sml = 0; sml <= 1; sml++){ if(!dp[pos][sum][sml]) continue; if(sml == 1){ REP(d,10){ (dp[pos+1][(sum+d)%D][1] += dp[pos][sum][1]) %= MOD; } } else{ int lim = N[pos] - '0'; for(int d = 0; d < lim; d++){ (dp[pos+1][(sum+d)%D][1] += dp[pos][sum][0]) %= MOD; } (dp[pos+1][(sum+lim)%D][0] += dp[pos][sum][0]) %= MOD; } } } } cout << (dp[N.length()][0][0]+dp[N.length()][0][1]-1)%MOD << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - 数 |
User | Bloody_Yulii |
Language | C++14 (GCC 5.4.1) |
Score | 4 |
Code Size | 2333 Byte |
Status | AC |
Exec Time | 53 ms |
Memory | 16640 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 | 6 ms | 16640 KB |
01 | AC | 34 ms | 16640 KB |
02 | AC | 53 ms | 16640 KB |
90 | AC | 6 ms | 16640 KB |
91 | AC | 6 ms | 16640 KB |