桁DPのフォーマット - 競プロPythonのスニペット置き場

桁DP

$N$ 以下の数のうち条件を満たすものを答えよというような問題で使える。

計算量
$O(Bk\log N)$ 　（ $k$ ：状態数、 $B$ ：桁に置ける数字の種類）

ソースコード
$N$ 以下に必ずなるかを表す添字 $less$ が肝となるが、遷移を書くのによく手間取る。 $less$ のことを考えなくても書けるソースコードを示す。
(!!!書き換えるとしたところを問題によって変える。)

l=[ord(i)-ord('0') for i in str(n)]
dig=len(l)
dp=[[[0,0] for _ in range(kmax)] for _ in range(dig+1)]     #kmax   !!!書き換える
dp[0][0][0]=1                                               #初期条件!!!書き換える
for i in range(dig):
    for less in range(2):
        for j in range(10):
            if less==0 and j>l[i]:
                break
            for k in range(kmax):                           #kmax   !!!書き換える
                #配るDP i+1桁目にjを置く k→k1に変化
                dp[i+1][k1][less|(j<l[i])]+=dp[i][k][less]  #遷移 !!!書き換える

例
TDPC-E
求めるもの
（N以下の正整数のうち各位の和がDの倍数であるものの個数）%1,000,000,007
$dp_{i,k,less}=$ （i桁目まで決めた時dで割ったあまりがkの個数、less:N以下必ずなるか）

d=int(input())
n=int(input())
l=[ord(i)-ord('0') for i in str(n)]
dig=len(l)
dp=[[[0,0] for _ in range(d)] for _ in range(dig+1)]        #kmax   !!!書き換える
dp[0][0][0]=1                                               #初期条件!!!書き換える
mod=10**9+7
for i in range(dig):
    for less in range(2):
        for j in range(10):
            if less==0 and j>l[i]:
                break
            for k in range(d):                              #kmax   !!!書き換える
                #配るDP i+1桁目にjを置く 各位の和をdで割ったあまりはk→(k+j)%dに変化
                dp[i+1][(k+j)%d][less|(j<l[i])]+=dp[i][k][less]  #遷移 !!!書き換える
                dp[i+1][(k+j)%d][less|(j<l[i])]%=mod

ans=sum(dp[-1][0])-1
ans%=mod
# dp[-1][0][0]:Nが条件を満たすか
# dp[-1][0][1]:N未満の数のうち条件を満たしている個数
# 1:N=0の場合は含まれないので引く

print(ans)

例題
TDPC-E
ABC029D
ABC117D
ARC127A 状態をもう一つ作り4次元で桁DPを行う

参考