Submission #5882878

---

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;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

const MOD = 10^^9 + 7;

void add(T)(ref T a, in T b) { a = (a + b) % MOD; }

long calc(string s, int d) {
    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;
    foreach (i; 0..n) {
        foreach (j; 0..2) {
            foreach (k; 0..d) {
                int lim = j == 1 ? 9 : s[i] - '0';
                foreach (m; 0..lim+1) {
                    add(dp[i + 1][j || m < lim][(k + m) % d], dp[i][j][k]);
                }
            }
        }
    }

    // -1 は 0 の分
    return (-1L + MOD + dp[n][0][0] + dp[n][1][0]) % MOD;
}

void main() {
    int d = readint;
    string s = read!string;
    writeln(calc(s, d));
}

Submission Info

Judge Result