更好的阅读体验：TonyYin’s Blog ↗
题目地址：AT4540 Digit Sum - 洛谷 _ 计算机科学教育新生态 ↗
#
求区间 中有多少个整数满足：其十进制表示的数字和为 的倍数。答案对 取模。
#
观察数据范围：.
再看题面，形如”求在数位限制下有多少满足条件的数“，想到数位 .
如果你没有学过数位 ，那么可以参考这篇博客 ↗。
如果你学过数位 ，那么现在考虑状态如何设置。
状态设置：
首先可以看出，这道题不需要前导零标记。
第二步需要思考 中需要存储什么前缀状态。通过题目描述可以比较容易的看出，我们只需要存储前缀数字和对 取模的余数即可，将其记为 ，
那么能对答案作出贡献的条件就是：前缀数字和 ，也就是 .
至此，根据数位 的套路，我们可以设置如下状态：
表示还有 位需要处理；
当前状态的前缀数字和 是 ；
前缀的最大值状态是 ，若前 位与题目给出的 相同，则 ，反之亦然。
状态转移：
于是可以使用记忆化搜索来实现数位 ，详见代码注释。
个人觉得注释还比较清晰，认真多看几遍是能看懂的。
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;
}由于加上取模之后不美观，上面的代码没有给 加取模，需要加上。（下面的代码中是有取模的）
#
放出完整代码，可以再重点看一下 solve() 函数里面的初始化。
关键部分的注释已经在上面了。
如果没有看懂，建议再读几遍这篇博客 ↗，或者自行百度学习数位 .
#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;
}