Submission #5890879

---

Source Code Expand

#include <bits/stdc++.h>
#define BASE 1000000007
using namespace std;

int main() {
    int d;
    string n;
    cin >> d >> n;
    int m = n.size();
    long dp[2][d][m + 1];
    for (int j = 0; j <= m; j++) {
        for (int i = 0; i < d; i++) {
            dp[0][i][j] = 0;
            dp[1][i][j] = 0;
        }
    }
    dp[1][0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < d; j++) {
            for (int k = 0; k < n[i - 1] - '0'; k++) {
                dp[0][(j + k) % d][i] += (dp[0][j][i - 1] + dp[1][j][i - 1]) % BASE;
                dp[0][(j + k) % d][i] %= BASE;
            }
            dp[0][(j + n[i - 1] - '0') % d][i] += dp[0][j][i - 1];
            dp[0][(j + n[i - 1] - '0') % d][i] %= BASE;
            dp[1][(j + n[i - 1] - '0') % d][i] += dp[1][j][i - 1];
            dp[1][(j + n[i - 1] - '0') % d][i] %= BASE;
            for (int k = n[i - 1] - '0' + 1; k < 10; k++) {
                dp[0][(j + k) % d][i] += dp[0][j][i - 1];
                dp[0][(j + k) % d][i] %= BASE;
            }
        }
    }
    cout << (BASE - 1 + dp[0][0][m] + dp[1][0][m]) % BASE << endl;
    return 0;
}

Submission Info

Judge Result