第一道数位 \(\text{dp}\)，检验一下自己懂没懂。
特别感谢 \(\text{yinhee}\) 大佬，他的讲解令我受益匪浅。
题目分析
\(dp_{pos,res,lim}\) 为当前枚举到从高位往低位数第 \(pos\) 位，数字和取模后的余数为 \(res\) 时的方案数，其中 \(lim\) 可以理解为一个布尔值，\(0\) 表示没有到上限，\(1\) 表示到了上限。
然后是一个数位 \(\text{dp}\) 的板子，我特别讲一下这一行代码：
tot+=dfs(pos-1,(res+i)%d,(lim!=0)&&(i==maxx));
其中 \(maxx\) 是当前枚举位可选的最大值。
这里就是在枚举第 \(pos-1\) 位，选择了 \(i\) 作为这位的数，\(res+i\) 就是新的数字和。而后面的判断条件就是在看枚举到目前为止，该数是否还与 \(k\) 的前缀相同，是就说明到目前为止还是最大的，否则就不是。
贴上代码
#include<bits/stdc++.h>
// #define int long long
#define ok printf("1")
#define no printf("0")
using namespace std;
int read(){
int 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*10+c-48;
c=getchar();
}
return x*f;
}
const int mod=1e9+7;
const int maxn=10010;
const int maxm=110;
int n,d;
int a[maxn];
int dp[maxn][maxm][2];
string s;
int dfs(int pos,int res,int lim){
if(pos==0){
if(res==0) return 1;
else return 0;
}
if(dp[pos][res][lim]!=-1) return dp[pos][res][lim];
int maxx=9,tot=0;
if(lim!=0) maxx=a[pos];
for(register int i=0;i<=maxx;++i){
tot+=dfs(pos-1,(res+i)%d,(lim!=0)&&(i==maxx));tot%=mod;
}
dp[pos][res][lim]=tot;
return tot;
}
inline void init(){
cin>>s;n=s.size();
cin>>d;
for(register int i=0;i<n;++i) a[n-i]=s[i]-48;
memset(dp,-1,sizeof(dp));
}
int main(){
init();
printf("%d",(dfs(n,0,1)-1+mod)%mod);
}