Educational DP Contest / DP まとめコンテスト
はい。桁DP練習中です。
https://atcoder.jp/contests/dp
S - Digit Sum
PyPy3
mod=10**9+7 k=input() d=int(input()) l=[int(i) for i in "0"+k] dp=[[[0]*(d+2),[0]*(d+2)] for _ in "ww"] dp[0][0][0]=1 for i,j in enumerate(l): if i==0: continue for p in range(d+1): if dp[i%2-1][0][p]: dp[i%2][0][[(p+j)%d,d][(p+j)%d==0]]=1 for q in range(j): dp[i%2][1][[[(p+q)%d,d][(p+q)%d==0],0][p==q==0]]+=1 if dp[i%2-1][1][p]: for q in range(10): dp[i%2][1][[[(p+q)%d,d][(p+q)%d==0],0][p==q==0]]+=dp[i%2-1][1][p] for p in range(d+2): dp[i%2-1][0][p]=0 dp[i%2-1][1][p]=0 dp[i%2][0][p]%=mod dp[i%2][1][p]%=mod print((dp[0][0][d]+dp[0][1][d]+dp[1][0][d]+dp[1][1][d])%mod)
丁度KとKより小さいことが確定しているものとに分ける。 それとDの倍数の状態を%dでチェックするのに本当にDの倍数のものと、単に合計で余り0になっているものがあるので別に分けて考えました。