Submission #5902709

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define RREP(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)

const ll MAX = 1e9+7;

ll dp[10001][2][101];
int D;
string N;

ll solve(int k, int big, int sum) {
  if (k == N.size()) return sum == 0;
  if (dp[k][big][sum] != -1) return dp[k][big][sum];

  ll ret = 0;
  int c = N[k] - '0';
  REP(i, big ? 10 : c+1) {
    int b = big == 1 || i < c;
    ret += solve(k+1, b, (sum+i)%D);
    ret %= MAX;
  }
  return dp[k][big][sum] = ret;
}

int main(int argc, char *argv[]) {
  cin >> D;
  cin >> N;
  if (D==1) {
    cout << N << endl;
    return 0;
  }
  fill_n(&dp[0][0][0], 10001*2*101, -1);
  solve(0, 0, 0);
  cout << dp[0][0][0] - 1<< endl;
  return 0;
}

Submission Info

Judge Result