桁DP $ dp[i桁まで見て][剰余がjで][Kより小さいか] のDPで解く $ dp[0][0][0] = 1 で他は0としておく 小さいかどうかは、Kちょうど->Kより小さいの方面でしか遷移しない Kより小さいならその桁は0~9までで遷移できる Kちょうどの場合、Kちょうどのままとその桁の数値未満の数字を使ってKより小さい状態にも遷移できる 0の…