题目大意
求 \([1, N]\) 中有多少个数在十进制表示下数码和是 \(D\) 的倍数。
数据范围：\(1\le N\le 10^{10000},1\le D\le 100\)。
思路
很明显的数位 dp。
这里采用了记忆化搜索来实现数位 dp。
记忆化搜索实现比较板子，不光写起来比较简单，而且容易扩展，所以建议大家都学习一下。
首先把上界 \(N\) 的每一位抠出来，然后进行填数，个人喜欢从最高位开始填。
加上记忆化，设 \(f(pos, r)\) 表示在没有顶上界和前导零的情况下，当前填到了第 \(pos\) 位，余数为 \(r\) 的数的个数。
然后在搜索过程中记一下当前数位和 \(\bmod p\) 等于多少，再简单转移一下即可，详细注释在代码中。
注意到状态数为 \(D\cdot\lg N\)，每次转移时最多枚举 \(10\) 个可填的数，所以时间复杂度为 \(O(D\cdot \lg N)\)，可以通过此题。
注意！由于最后要 \(-1\)，所以为防止减为负数要先加上模数再取模。
\(\texttt{Code:}\)
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010, M = 110, mod = 1e9 + 7;
typedef long long ll;
char s[N];
int len, d;
int f[N][M];
vector<int> num;
//记忆化搜索
//pos 记录当前填到了哪一位，r 记录填完 pos + 1 到 len - 1 位后数位和模 d 的值
//limit 记录当前有没有顶上界，zero 记录当前是不是前导零
ll dfs(int pos, int r, bool limit, bool zero) {
//边界，若填完了就检查一下是否符合条件
if(pos < 0) return (r == 0);
//若不顶上界且没有前导零就记忆化，因为顶上界和前导零是特殊情况，满足条件的数可能和普通情况不同
if(!limit && !zero && f[pos][r] != -1) return f[pos][r];
//看一下当前这位需不需要顶上界，若前面填的数都是贴着上界的，这一位最多只能填到 num[pos]，否则不受限
int mx = (limit ? num[pos] : 9);
ll res = 0;
//枚举第 pos 位填什么
for(int i = 0; i <= mx; i++)
//去填下一位，更新当前余数，看下一位是不是顶上界，看下一位是不是前导零
res = (res + dfs(pos - 1, (r + i) % d, limit && (i == num[pos]), zero && (!i))) % mod;
//若不顶上界且没有前导零就记忆化
if(!limit && !zero) f[pos][r] = res;
return res;
}
ll calc(char str[]) {
//把每一位抠出来，注意是倒过来的
for(int i = len - 1; i >= 0; i--)
num.push_back(s[i] - '0');
memset(f, -1, sizeof f);
return dfs(len - 1, 0, 1, 1);
}
int main() {
scanf("%s%d", s, &d);
len = strlen(s);
//因为我们搜索考虑了 0，最后要把一减去
printf("%lld", (calc(s) + mod - 1) % mod);
return 0;
}