1
int a[20];
2
ll dp[20][StateSize]; // 记忆化数组，注意：不要把 limit 记进去！
3

4
// pos: 当前处理到第几位（从高到低，len -> 1）
5
// state: 当前的状态（比如：数字之和 % D，或者已有的非零个数）
6
// limit: 当前位是否受到 N 的最高位限制
7
// lead: 当前是否处于前导零状态（视题目而定是否需要）
8
ll dfs(int pos, int state, bool limit, bool lead) {
9
    // 1. 递归边界：填完了所有位
10
    if (pos == 0) {
11
        // 返回 1 表示找到一个合法数字
12
        // 或者检查 state 是否满足最终条件（例如 sum % D == 0）
13
        return 1;
14
    }
15

16
    // 2. 记忆化搜索
17
    // 只有当 !limit && !lead 时，状态才是通用的，可以读取/记录 dp
18
    // 解释：如果 limit=true，说明当前是在贴着 N 的边缘走，这个状态是特例，不能复用。
19
    if (!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
20

21
    // 3. 确定当前位能填的最大数字
22
    // 如果 limit 为 true，只能填到 a[pos]；否则可以填到 9
23
    int up = limit ? a[pos] : 9;
24

25
    ll ans = 0;
26

27
    // 4. 枚举当前位填什么数字 i
28
    for (int i = 0; i <= up; ++i) {
29
        // 更新状态
30
        // 比如题目要求数位之和： new_state = (state + i) % D
31
        // 比如题目要求非零个数： new_state = state + (i != 0)
32

33
        // 处理前导零对 state 的影响：
34
        // 如果原本是前导零且当前填了 0，state 通常不变
35

36
        // 递归
37
        // new_limit 的逻辑：只有当前本来就受限(limit=true) 且 当前填了最大值(i==up) 时，下一位才继续受限
38
        // new_lead 的逻辑：当前是前导零 且 当前填了 0，下一位还是前导零
39
        ans += dfs(pos - 1, new_state, limit && (i == up), lead && (i == 0));
40
    }
41

42
    // 5. 记录 memo
43
    if (!limit && !lead) dp[pos][state] = ans;
44

45
    return ans;
46
}
47

48
ll solve(string s) {
49
    int len = s.length();
50
    // 把字符串转成 int 数组，注意顺序，通常 a[len] 是最高位，a[1] 是最低位
51
    for (int i = 0; i < len; ++i) a[len - i] = s[i] - '0';
52

53
    // 初始化 dp 数组，通常为 -1
54
    memset(dp, -1, sizeof(dp));
55

56
    return dfs(len, 0, true, true);
57
}