Submission #6438416

---

Source Code Expand

#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = INF + 7;

int dp[100001][2][100];

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

    int len = (int)N.size();

    dp[0][0][0] = 1;
    for(int i = 0; i < len; i++){
        for(int smaller = 0; smaller < 2; smaller++){
            int limit = smaller ? 9 : N[i] - '0';
            for(int j = 0; j < D; j++){
                for(int k = 0; k <= limit; k++){
                    (dp[i+1][smaller or k < limit][(j+k)%D] += dp[i][smaller][j]) %= MOD;
                }
            }
        }
    }

    cout << (dp[len][0][0] + dp[len][1][0] - 1) % MOD << '\n';

    return 0;
}

Submission Info

Judge Result