はまやんはまやんはまやん

hamayanhamayan's blog

Digit Sum [Educational DP Contest / DP まとめコンテスト S]

https://atcoder.jp/contests/dp/tasks/dp_s

前提知識

解説

https://atcoder.jp/contests/dp/submissions/3949534

桁DPをする。
dp[dgt][d][isless] := 上からdgt桁目まで確定していて、各桁の数字の総和modDがdで、K未満かどうかがisless(isless=1なら既にK未満)である組み合わせ
難しいように見えるが、桁DPはdp[dgt][??][isless]というテンプレがあるので、そこから派生してDPを定義していく。
各状態について、次の桁の数を10通り試すので、計算量はO(KD)

string K; int D, N;
mint dp[10101][101][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K >> D;
    int N = K.length();
 
    dp[0][0][0] = 1;
    rep(dgt, 0, N) rep(d, 0, D) rep(isless, 0, 2) {
        int c = K[dgt] - '0';
        rep(nxt, 0, 10) {
            if (nxt < c) dp[dgt + 1][(d + nxt) % D][1] += dp[dgt][d][isless];
            else if(nxt == c) dp[dgt + 1][(d + nxt) % D][isless] += dp[dgt][d][isless];
            else {
                if(isless) dp[dgt + 1][(d + nxt) % D][isless] += dp[dgt][d][isless];
            }
        }
    }
 
    cout << dp[N][0][0] + dp[N][0][1] - 1 << endl;
}