Submission #6361558

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
const int mod=1e9+7;

int main(){
    int d;cin>>d;
    string s;cin>>s;
    int dig=s.size();
    int n[dig];
    rep(i,dig){
        n[i]=s[i]-'0';
    }
    ll dp[dig+1][d][2];
    memset(dp,0,sizeof(dp));
    dp[0][0][1]=1;
    rep(i,dig){
        rep(j,d){
            rep(k,10){
                dp[i+1][(j+k)%d][0]+=dp[i][j][0];
                dp[i+1][(j+k)%d][0]%=mod;
            }
            rep(k,n[i]){
                dp[i+1][(j+k)%d][0]+=dp[i][j][1];
                dp[i+1][(j+k)%d][0]%=mod;
            }
            dp[i+1][(j+n[i])%d][1]+=dp[i][j][1];
            dp[i+1][(j+n[i])%d][1]%=mod;
        }
    }
    cout<<(dp[dig][0][0]+dp[dig][0][1]-1)%mod<<endl;
}

Submission Info

Judge Result