DP S

ある数K以下の自然数で、条件を満たすものがいくつあるか、という問題

素朴にK個の数を調べることはKがやたらでかいのでできない前提

桁DPはもらうDPよりも配るDPの方が圧倒的に書きやすい

なるほど、以前試してバグらせた時はもらう実装でやってた

まずはシンプルに「K以下の自然数の個数を数え上げる」をDPで考える

https://gyazo.com/c9063ac33df020121c1f8d9ce839578a

57以下の自然数の数を数えている

ゼロを含むので「57未満が57個、イコールが1個」となっている

「先頭i桁」を定義域とし、そこまでで「K以下である数」「イコールKである数」の個数を値とするDP

ところで「イコールKである数」は常に1なのだからテーブルで持つ必要はないよね

解説などではテーブルで持ってるものが多くて、その方が複雑な問題だと実装の都合が良いことがあるのかな

今回の問題では追加の条件「Dで割り切れる」のチェックのためにDで割ったあまりごとに数え分けているが、僕の実装では「イコールK」にはテーブルを用意しなかった

code:python

def solve(N, D):

equal = 0

for digit in N:

for new_digit in range(10):

for d in range(D):

if new_digit < digit:

for d in range(D):

less = new_less

equal += digit

equal %= D

ret -= 1 # for x = 0

if equal == 0: # for x = N

ret += 1

return ret % MOD

old version

code:python

def solve(K, D):

N = len(K)

border = 0

for i in range(N):

for j in range(10):

for d in range(D):

border %= D

ret += (border == 0)

return ret % MOD