Submission #1604386

---

Source Code Expand

import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

int calc(string s, int d) {
    const MOD = 1_000_000_007;

    int n = cast(int) s.length;
    auto dp = new int[][][](n + 1, 2, d);
    // dp[i][j][k]
    // i: 上から i 桁目まで
    // j: n 未満か
    // k: mod d

    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < d; k++) {
                int lim = j == 1 ? 9 : s[i] - '0';
                for (int m = 0; m <= lim; m++) {
                    (dp[i + 1][j || m < lim][(k + m) % d] += dp[i][j][k]) %= MOD;
                }
            }
        }
    }

    int ans = 0;
    for (int j = 0; j < 2; j++) {
        ans = (ans + dp[n][j][0]) % MOD;
    }
    return ans - 1; // -1 は 0 の分
}

void main() {
    int d = readint;
    string s = readln.chomp;

    writeln(calc(s, d));
}

Submission Info

Judge Result