Submission #5859000

---

Source Code Expand

#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

typedef vector<int> vi;
typedef vector<vi>  vvi;

const int MOD = 1000000007;

int main()
{
    int D; cin >> D;
    string N; cin >> N;

    // nth-digit, less, rem
    vector<vvi> dp(N.size()+1, vvi(2, vi(D, 0)));
    dp[0][0][0] = 1;

    rep(n,N.size()) rep(l,2) rep(d,D) {
        if(dp[n][l][d] == 0)
            continue;

        int Mi = l? 10: N[n]-'0'+1;
        rep(i, Mi) {
            if(!l && i == Mi-1) {
                /* limit */
                dp[n+1][0][(d+i)%D] = (dp[n][l][d] + dp[n+1][0][(d+i)%D]) % MOD;
            } else {
                /* not limit */
                dp[n+1][1][(d+i)%D] = (dp[n][l][d] + dp[n+1][1][(d+i)%D]) % MOD;
            }
        }
    }

    cout << dp[N.size()][0][0] + dp[N.size()][1][0] - 1 << endl;

    return 0;
}

Submission Info

Judge Result