Educational DP Contest S - Digit Sum
桁DP
$ dp[i桁まで見て][剰余がjで][Kより小さいか] のDPで解く
$ dp[0][0][0] = 1 で他は0としておく
小さいかどうかは、Kちょうど->Kより小さいの方面でしか遷移しない
Kより小さいならその桁は0~9までで遷移できる
Kちょうどの場合、Kちょうどのままとその桁の数値未満の数字を使ってKより小さい状態にも遷移できる
0の場合が含まれてしまっているので$ (dp[n][0][0] + dp[n][0][1] - 1 + MOD) % MOD が答え
各桁での遷移は高々10回なので$ O(D\log K)