题目解析
我怎么连数位dp都不会喏，降智了，写了1h
顺便用这道数位(dp)入门题复习一下数位dp吧
这道题是否统计答案和数位和模(D)的余数相关，所以可以定义(f[i][j][k])表示余数为(i)，算到到第(j)位 前缀是否与(k)完全一致(用于判断这一位上限)
然后记忆化搜索转移就可以了，至于复杂度……这种数位题也只能这么做不是，也没有什么优化的余地。
最后注意要减去(0)的情况
►Code View
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define N 10005
#define D 105
#define MOD 1000000007
#define INF 0x3f3f3f3f3f3f3f3f
#define LL long long
LL rd()
{
LL x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return f*x;
}
char S[N];
int n,k[N];
int d;
LL ans,f[D][N][2];//f[i][j][k] 余数为i 到第j位 前缀是否与k完全一致(用于判断这一位上限
LL dfs(int r,int p,int s)
{
if(p==n+1)
{
if(r==0) return 1;//找到一种方案 之前脑残 写的f[r][p][s]
return 0;
}
if(f[r][p][s]!=-1) return f[r][p][s];
int lim=9;
LL res=0;
if(s==1) lim=k[p];
for(int i=0;i<=lim;i++)
res=(res+dfs((r+i)%d,p+1,s&(i==k[p])))%MOD;
return f[r][p][s]=res;
}
int main()
{
scanf("%s",S+1);
n=strlen(S+1);
for(int i=1;i<=n;i++)
k[i]=S[i]-'0';
d=rd();
memset(f,-1,sizeof(f));
ans=dfs(0,1,1);
printf("%lld
",(ans-1+MOD)%MOD);//最后还要减去0
return 0;
}