Submission #2546934
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <functional>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using vb = vector<char>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define RREP(i, a, b) for (int i = (int)(b) - 1; i >= a; i--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define mp(a, b) make_pair(a,b)
#define fi first
#define sn second
#define decpii(p) p.fi--,p.sn--;
#ifdef LOCAL
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define dumpn(c) cerr << "> " << #c << " = " << (c) << ", ";
#else
#define dump(c) ;
#define dumpn(c) ;
#endif
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '(' << p.first << ',' << p.second << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
os << '[';
rep(i, (int) a.size())os << (i ? " " : "") << a[i];
return os << ']';
}
const int INF = 1 << 29;
const int MOD = 1000000007;
int dxf[] = {1, 0, -1, 0};
int dyf[] = {0, -1, 0, 1};
template<class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
inline vi uni(vi &vec) {
sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
return vec;
}
struct ____ {
____() {
cin.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(20);
};
} ________;
auto solve() {
int M;
string S;
cin >> M >> S;
int n = S.length();
vector<vvi> dp(n + 1, vvi(2, vi(M, 0)));
dp[0][0][0] = 1;
rep(i, n) {
rep(isless, 2) {
rep(mod, M) {
int lim = isless ? 9 : S[i] - '0';
rep(digit, lim + 1) {
(dp[i+1][isless || digit < lim][(mod + digit) % M] += dp[i][isless][mod]) %= MOD;
}
}
}
}
ll res = 0;
rep(isless, 2) res += dp[n][isless][0];
return (res-1) % MOD;
}
int main() {
// cout << (solve() ? "yes" : "no") << endl;
cout << solve() << endl;
// solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
E - 数 |
User |
palpal |
Language |
C++14 (GCC 5.4.1) |
Score |
4 |
Code Size |
2862 Byte |
Status |
AC |
Exec Time |
110 ms |
Memory |
9088 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 |
384 KB |
01 |
AC |
67 ms |
5888 KB |
02 |
AC |
110 ms |
9088 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |