Submission #1242249

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

long long M=1000000007;
int main(int argc, char const *argv[]) {
  int d;cin>>d;
  string s;cin>>s;
  int n=s.length();
  vector<vector<long long>> dp1(n+1,vector<long long>(d)),dp2(n+1,vector<long long>(d));
  dp1[0][0]=1;
  dp2[0][0]=1;
  for(int i=0;i<n;++i){
    for(int j=0;j<d;++j){
      for(int k=0;k<=9;++k){
        dp1[i+1][(j+k)%d]+=dp1[i][j];
        dp1[i+1][(j+k)%d]%=M;
      }
      int p=stoi(s.substr(n-1-i,1));
      for(int k=0;k<p;++k){
        dp2[i+1][j]+=dp1[i][(j-k+10*d)%d];
        dp2[i+1][j]%=M;
      }
      dp2[i+1][(j+p)%d]+=dp2[i][j];
      dp2[i+1][(j+p)%d]%=M;
    }
  }
  cout<<dp2[n][0]-1<<endl;
  return 0;
}

Submission Info

Judge Result