Submission #3778881
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ALL(x) (x).begin(), (x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807LL
#define LMIN -9223372036854775807LL
using ll = int64_t;
template<typename T>
using vec = vector<T>;
using P = pair<ll, ll>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
fill((T *)array, (T *)(array + N), val);
}
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//ll pas[5001][5002];
string s;
ll n, d;
ll dp[10003][2][102];
ll rec(ll i, bool tit, ll sum){
ll &tmp = dp[i][tit][sum];
if(~tmp)return tmp;
if(i == n){
return (sum % d == 0);
}
tmp = 0;
ll MX = (tit ? s[i] - '0' : 9);
for(int j = 0;j <= MX;j++){
tmp += rec(i + 1,tit && j == MX,(sum + j) % d);
tmp %= MOD;
}
return tmp;
}
signed main(){
IOS;
cin >> d >> s;
n = s.size();
Fill(dp, -1);
dump(rec(0, true, 0) - 1);
}
Submission Info
Submission Time |
|
Task |
E - 数 |
User |
jgvt5ti |
Language |
C++14 (GCC 5.4.1) |
Score |
4 |
Code Size |
1137 Byte |
Status |
AC |
Exec Time |
149 ms |
Memory |
17024 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 |
8 ms |
16256 KB |
01 |
AC |
93 ms |
17024 KB |
02 |
AC |
149 ms |
17024 KB |
90 |
AC |
7 ms |
16256 KB |
91 |
AC |
7 ms |
16256 KB |