Submission #18296628

---

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] % 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