Submission #18296806

---

Source Code Expand

#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

Judge Result