Contest Duration: - (local time) (300 minutes) Back to Home

Submission #18296806

Source Code Expand

Copy
```#include<bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i, 0, n)
#define all(x) (x).begin(),(x).end()
const int INF = 1e9+1;
using namespace std;
using ll = long long;
using p = pair<int, int>;
using v = vector<int>;

int main(){
int R;
string S;
cin >> R >> S;
int N = S.size();
ll Q = 1e9+7;
vector<vector<vector<ll>>> dp(N+1, vector<vector<ll>>(2, vector<ll>(R, 0)));
dp[0][0][0] = 1;

REP(n, N) {
int D = S[n] - '0';
// cout << "D: " << D << endl;
REP(f, 2) {
REP(r, R) {
for(int d=0; d <= (f ? 9 : D); d++) {
dp[n+1][f || (d < D)][(r+d)%R] += dp[n][f][r];
dp[n+1][f || (d < D)][(r+d)%R] %= Q;
}
}
}
}
// REP(i, N+1) {
//   cout << "n: " << i << endl;
//   REP(j, 2) {
//     cout << "f: " << j << endl;
//     REP(k, R) {
//       cout << dp[i][j][k] << " ";
//     }
//     cout << endl;
//   }
//   cout << "-------------------\n";
// }
cout << (dp[N][0][0] + dp[N][1][0] - 1) << endl;;

return 0;
}```

#### Submission Info

Submission Time 2020-11-22 16:16:42+0900 E - 数 AceK C++ (GCC 9.2.1) 4 1094 Byte AC 110 ms 19560 KB

#### Judge Result

Set Name All
Score / Max Score 4 / 4
Status
 AC × 5
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 9 ms 3652 KB
01 AC 69 ms 13584 KB
02 AC 110 ms 19560 KB
90 AC 9 ms 3344 KB
91 AC 2 ms 3524 KB