$\rm{Description}$

求区间 $[1, k]$ 中有多少个整数满足：其十进制表示的数字和为 $D$ 的倍数。答案对 $1e9+7$ 取模。

$\rm{Solution}$

观察数据范围：$1\leq k\leq 10^{10000}$.

再看题面，形如”求在数位限制下有多少满足条件的数“，想到数位 $\rm{DP}$.

如果你没有学过数位 $\rm{DP}$，那么可以参考这篇博客，我就是照着这篇博客学懂的。

如果你学过数位 $\rm{DP}$，那么现在考虑状态如何设置。

状态设置：

首先可以看出，这道题不需要前导零标记。

第二步需要思考 $\rm{DP}$ 中需要存储什么前缀状态。通过题目描述可以比较容易的看出，我们只需要存储前缀数字和对 $D$ 取模的余数即可，将其记为 $\rm{pre}$，

那么能对答案作出贡献的条件就是：前缀数字和 $\bmod D =0$，也就是 $pre = 0$.

至此，根据数位 $\rm{DP}$ 的套路，我们可以设置如下状态：

$\rm{DP}[pos][pre][sta]$ 表示还有 $pos$ 位需要处理；

当前状态的前缀数字和 $\bmod D$ 是 $pre$；

前缀的最大值状态是 $sta$，若前 $len-pos$ 位与题目给出的 $k$ 相同，则 $sta=0$，反之亦然。

状态转移：

于是可以使用记忆化搜索来实现数位 $\rm{DP}$，详见代码注释。

个人觉得注释还比较清晰，认真多看几遍是能看懂的。

int dfs(int pos, int res, int sta) {
	if(pos == 0) return res == 0; //能对答案作出贡献的条件：前缀数字和 mod D == 0
	if(dp[pos][res][sta] != -1) return dp[pos][res][sta]; //记忆化搜索
	int ret = 0, maxx = 9; //ret是函数返回值，maxx是当前位可选的最大值
    if(sta) maxx = num[pos]; //如果当前前缀与k的前缀相同，那么这一位最大值就是num[pos]
	for(int i = 0; i <= maxx; i++) { //之后遍历这一位可选的数字
		ret += dfs(pos - 1, (res + i) % d, sta && (i == maxx));
        //pos - 1: 继续看下一位
        //(res + i) % d: 把前缀数字和加上新选的这一位
        //sta && (i == maxx): 前缀and当前这一位, 都与k的前缀相同，那么新的前缀还是最大值状态 
	}
	dp[pos][res][sta] = ret;//记忆化
	return ret;
}

由于加上取模之后不美观，上面的代码没有给 $ret$ 加取模，需要加上。（下面的代码中是有取模的）

$\rm{Code}$

放出完整代码，可以再重点看一下 solve() 函数里面的初始化。

关键部分的注释已经在上面了。

如果没有看懂，建议再读几遍这篇博客，或者自行百度学习数位 $\rm{DP}$.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXLEN = 10008;
const int MAXD = 108;
const int mod = 1e9 + 7;
int d, num[MAXLEN];
string s;
int dp[MAXLEN][MAXD][2];
int dfs(int pos, int res, int sta) {
	if(pos == 0) return (res == 0);
	if(dp[pos][res][sta] != -1) return dp[pos][res][sta];
	int ret = 0, maxx = 9;
	if(sta) maxx = num[pos];
	for(int i = 0; i <= maxx; i++) {
		ret = (ret + dfs(pos - 1, (res + i) % d, sta && (i == maxx))) % mod;
	}
	dp[pos][res][sta] = ret;
	return ret;
}
int solve() {
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i < s.length(); i++) {
		num[i + 1] = s[s.length() - i - 1] - '0';
	}
	return dfs(s.length(), 0, 1);
}
signed main() {
	cin >> s;
	scanf("%lld", &d);
	printf("%lld\n", ((solve() - 1) % mod + mod) % mod);
	return 0;
}