Typical DP Contest

Submission #5882878

Source codeソースコード

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

Task問題 E - 数
User nameユーザ名 noriok
Created time投稿日時
Language言語 D (DMD64 v2.070.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 1218 Byte
File nameファイル名
Exec time実行時間 97 ms
Memory usageメモリ使用量 13436 KB

Test case

Set

Set name Score得点 / Max score Cases
All 4 / 4 00,01,02,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 2 ms 380 KB
01 AC 59 ms 6780 KB
02 AC 97 ms 13436 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB