Typical DP Contest

はい。桁DP練習中です。
https://atcoder.jp/contests/tdpc

E - 数

▶クリックで開閉

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n)  for(int i=0;i<n;++i)
#define sc1(a)  scanf("%d",&a)

char c[10005];
int dp[10005][2][105];
int main(){
    int mod=1000000007;
    int d,n,m=0,ans=0;
    sc1(d);
    dp[0][0][0]=1;
    scanf("%s",c);
    long p=strlen(c);
    for(long i=0;i<p;i++) {
        int x=c[i]-'0';
        rep(j,101) {
            if (dp[i][0][j]>0 || dp[i][1][j]>0) rep(k,10) {
                    if (k==x) dp[i+1][0][(j+k)%d]+=dp[i][0][j];
                    if (k<x) dp[i+1][1][(j+k)%d]+=dp[i][0][j];
                    dp[i+1][1][(j+k)%d]+=dp[i][1][j];
                    dp[i+1][0][(j+k)%d]%=mod; dp[i+1][1][(j+k)%d]%=mod;
            }
        }
    }
    ans+=dp[p][0][0]; ans+=dp[p][1][0]; ans%=mod;
    printf("%d\n",ans-1);
    return 0;
}

mod=10**9+7
d=int(input())
n="0"+input()
x=len(n)
l=[int(i) for i in n]
ans=0
dp1=[[0]*101 ,[0]*101]
dp2=[[0]*101 ,[0]*101]
dp1[0][0]=1
for i in range(1,x):
    for j in range(0,d+1):
        if dp1[i%2-1][j]:
            for k in range(l[i]):
                k=[(k+j)%d,d][(k+j)%d==0]
                dp2[i%2][k]+=1
                dp2[i%2][k]%=mod
            x=(j+l[i])%d
            if x==0: x=d
            dp1[i%2][x]=1 #余りを調べて該当するトコに1
            dp1[i%2-1][j]=0 #1つ前の桁の情報は要らなくなるので0
        if dp2[i%2-1][j]:
            for k in range(10):
                k=[(k+j)%d,d][(k+j)%d==0]
                dp2[i%2][k]+=dp2[i%2-1][j] #頑張る
                dp2[i%2][k]%=mod
            dp2[i%2-1][j]=0
 
print((dp1[0][d]+dp1[1][d]+dp2[0][d]+dp2[1][d]-1)%mod)

dp1はNより小さいことが確定していない場合用、dp2はNより小さいことが確定している場合用。DPの遷移の処理をしていく時に2つ前の桁の情報は要らないので2次元配列に。中身はDの倍数であるかを数えるためにD+1の分だけあれば大丈夫かな。
dp1の更新は1つ前の桁までの和のトコに新しく見る桁の数を足して%dで余りを調べて該当するトコに1を。1つ前の桁の情報は要らなくなるので0に。
dp2の更新はdp1も使いつつ頑張る。