题意简洁明了,自行理解

思路

看到题目要求是在1~k中各位数字之和%D为0的数的个数，像这种求1个区间内求含有一个性质的数的数量的题目,
自然想到的就是数位DP。

实现

数位DP的底层逻辑是从高位向低位填数，在这个过程中进行相应前缀和DP。
这种DP的实现过程都打差不差，这里就不赘述了。

如果数位DP不会或忘了的，学习一下这几道题： E36 E37 E38

细节

最后讲以下几个细节：
1.题目中k的范围到了10^10000，__int128和long double都存不下，所以用字符串string或char，再用num数组记录
每一位的数字，记得拆分和减'0'。
2.数位DP是用前缀和的思想来求解，本来应该是solve(k)-solve(1)，但solve(1)显而易见，它的值为1
(因为0%任何数都是零)，所以我们就可以省掉传入的部分，直接solve()-1即可，也别忘了%(1e9+7)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll P=1e9+7;
ll d,num[10010],f[10010][110][2];
//f[i][j]表示dp到第i位(从高位到低位)时数字和%D为j
//f[i][j][0]代表此时后面的位可以随便填,即现在数的前缀小于要求边界的前缀
//f[i][j][1]代表此时的前缀等于要求边界的前缀,后面能填的数也受到限制
//i--pos,j--res,0/1--sta 
string s;
ll dfs(ll pos,ll res,ll sta)
{
	if(!pos)return (res==0);
	//填到最后一位,如果已满足%D==0的要求,就能增加一种情况 
	if(f[pos][res][sta]!=-1)return f[pos][res][sta];//已经填过了 
	ll ret=0,mx=9;//ret为此时的方案数,mx为这一位能填的最大的数 
	if(sta)mx=num[pos];//前缀与边界前缀相等,最高只能填边界这位数 
	for(ll i=0;i<=mx;i++)ret=(ret+dfs(pos-1,(res+i)%d,sta&&(i==mx)))%P;
	//枚举这一位能填的数并继续向下填 
	f[pos][res][sta]=ret;//记忆化 
	return ret;
}
ll solve()
{
	memset(f,-1,sizeof f);
	for(ll i=0;i<s.length();i++)num[i+1]=s[s.length()-i-1]-'0';
	return dfs(s.length(),0,1);//遍历答案 
}
int main()
{
	cin>>s>>d;
	cout<<((solve()-1)%P+P)%P<<'\n';
	return 0;
}