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; }