普通动态规划常沿数组位置推进，数位 DP 则沿一个数的十进制位推进。它解决的不是“把所有数逐个检查”，而是把拥有相同前缀状态的大量整数一次计数。

本文用三道题逐层增加状态：1036C 只记录用了几个非零位；628D 同时记录位置规则、模 m 余数和上界关系；55D 再把“被每个非零数字整除”压缩为模 2520 的余数与有限个 LCM 状态。

1. 官方信息与学习顺序

以下题名、难度、标签与约束于 2026-09-15 通过 Codeforces 官方题目页核对。

题目 难度 官方标签 主要约束 本文训练点
1036C · Classy Numbers 1900 combinatorics、dp T≤10^4，R≤10^18 tight 与非零位计数
628D · Magic Numbers 2200 dp m≤2000，上下界等长且至多 2000 位 位置限制、余数、等长区间
55D · Beautiful numbers 2500 dp、number theory t≤10，R≤9×10^18 2520 余数、非零数字 LCM 压缩

三题都使用区间计数思想。定义 F(x) 为满足条件且不超过 x 的数的数量，则闭区间答案通常写成：

1
answer(L,R) = F(R) - F(L-1)

628D 的上下界保证位数相同，本文会展示另一种不必对长字符串做减一的等价写法。

2. 数位 DP 的共同骨架

从最高位向最低位填数字时，状态通常包含：

  • pos：正在决定第几位；
  • 与题目条件有关的摘要，例如非零位数、当前余数或数字 LCM；
  • tight：此前前缀是否与上界完全相同。

若 tight=true，当前位置最多填上界对应数字；若填得更小，后续所有位都可以自由取 0 到 9，新的 tight=false。若此前已经更小，当前位置不再受上界数字限制。

旧状态 当前选择 新状态
前缀等于上界 当前位等于上界位 仍然 tight=true
前缀等于上界 当前位更小 变为 tight=false
前缀已经更小 任意合法数字 保持 tight=false

只对 tight=false 的状态记忆化最方便，因为它的答案不再依赖上界后缀的具体内容。

3. 第一题：1036C Classy Numbers

3.1 题意与状态

一个正整数的十进制表示中，非零数字不超过 3 个，就称为 classy number。每次给出 [L,R]，统计区间内有多少个这样的数。

R 可以达到 10^18，逐个检查显然不可行。填前缀时，未来只需要知道已经用了多少个非零数字：

1
dfs(pos, used, tight)

选择当前数字 digit 后：

1
nextUsed = used + (digit != 0)

若 nextUsed>3，这条分支立即停止。前导零不会增加 used，所以不需要额外的 started 状态。DP 会把整数 0 计入 F(x)，但题目保证 L≥1，在 F(R)-F(L-1) 中它会自动抵消。

3.2 手工计数

以不超过 9999 的数为例，恰有 k 个非零位时，先从 4 个位置选 k 个，再为每个位置选择 1 到 9：

非零位数 k 数量
0 C(4,0)=1，只有 0000
1 C(4,1)×9=36
2 C(4,2)×9²=486
3 C(4,3)×9³=2916
4 不合法

这个组合式只能直接处理全是 9 的上界。对 5072 之类的任意上界，tight 会自动分开“仍贴着 5072”和“前缀已经更小”两类情况。

3.3 正确性证明

状态记录了决定未来合法性所需的全部信息：当前位置、已使用非零位数以及前缀与上界的关系。转移枚举当前位所有不超过限制的数字，每个不超过上界的定长十进制串对应唯一一条路径，且不会产生重复。

超过 3 个非零位的路径被舍弃，其他路径在全部位填完时贡献 1。因此 F(x) 恰好统计 [0,x] 中的合法整数；两个前缀计数相减后，得到 [L,R] 的答案。

3.4 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstring>
#include <functional>
#include <iostream>
#include <string>

using namespace std;

long long countUpTo(long long bound) {
    string digits = to_string(bound);
    long long memo[20][4];
    memset(memo, -1, sizeof(memo));

    function<long long(int, int, bool)> dfs = [&](int position, int used, bool tight) -> long long {
        if (used > 3) return 0;
        if (position == static_cast<int>(digits.size())) return 1;
        if (!tight && memo[position][used] != -1) return memo[position][used];

        int limit = tight ? digits[position] - '0' : 9;
        long long result = 0;
        for (int digit = 0; digit <= limit; ++digit) {
            result += dfs(position + 1, used + (digit != 0), tight && digit == limit);
        }

        if (!tight) memo[position][used] = result;
        return result;
    };

    return dfs(0, 0, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        long long left, right;
        cin >> left >> right;
        cout << countUpTo(right) - countUpTo(left - 1) << '\n';
    }
}

最多 19 个十进制位，每个非紧状态只有 4 种 used，每次转移枚举 10 个数字。单个上界的状态量是常数级，10^4 组询问也能通过；递归深度不超过 19。

4. 第二题：628D Magic Numbers

4.1 位置从 1 开始，限制并不对称

给定 m 与数字 d。一个数满足：十进制表示的所有偶数位置必须是 d，所有奇数位置都不能是 d；同时这个数要能被 m 整除。上下界 a,b 没有前导零、长度相同且不超过 2000。

例如 d=7 时，17 合法：第 1 位不是 7，第 2 位是 7。单独的 7 反而不合法，因为数字 7 出现在奇数位置。

本文代码用从 0 开始的 position：

数学位置 代码下标 允许数字
1、3、5…… 0、2、4…… 不能等于 d
2、4、6…… 1、3、5…… 必须等于 d

第一位还必须从 1 开始，避免生成前导零。

4.2 余数怎样转移

设当前前缀除以 m 的余数为 remainder，末尾追加 digit 后：

1
nextRemainder = (remainder × 10 + digit) mod m

DP 只保留 m 种余数，不需要保存可能长达 2000 位的前缀整数。状态为当前位置、是否贴着上界、当前余数；位置规则由循环下标直接判断，不另占状态。

4.3 为什么不用计算 a-1

对等长正整数字符串定义 F(s)：满足位置规则、能被 m 整除且不超过 s 的同长度整数数量。闭区间可写为：

1
F(b) - F(a) + valid(a)

其中 valid(a) 在 a 自身满足两项条件时为 1，否则为 0。这样避免对最多 2000 位的字符串执行借位减一，也避免 1000...0 - 1 后位数缩短造成额外分支。

4.4 官方第一组样例

m=2,d=6,a=10,b=99。两位数的第二位必须是 6，第一位不能是 6；同时偶数末位 6 天然保证整除 2。

十位可选 形成的数 是否计入
1,2,3,4,5 16,26,36,46,56 是
6 66 否，奇数位置出现 6
7,8,9 76,86,96 是

答案为 8。

4.5 正确性证明

DP 从左到右枚举每个同长度、无前导零且不超过上界的十进制串。奇偶位置过滤保证数字 d 恰好出现在偶数位置，余数转移保持当前前缀模 m 的真实值。全部位完成时只接受余数 0，所以 F(s) 的含义准确。

每个候选整数的十进制表示唯一，因此不会漏计或重复。F(b)-F(a) 去掉所有小于等于 a 的候选，再按 a 是否有效补回边界，恰好留下闭区间 [a,b]。

4.6 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <string>
#include <vector>

using namespace std;

constexpr int MOD = 1000000007;

int divisorMod;
int magicDigit;

void addModulo(int& target, int value) {
    target += value;
    if (target >= MOD) target -= MOD;
}

int countUpTo(const string& bound) {
    vector<vector<int>> dp(2, vector<int>(divisorMod, 0));
    dp[1][0] = 1;

    for (int position = 0; position < static_cast<int>(bound.size()); ++position) {
        vector<vector<int>> next(2, vector<int>(divisorMod, 0));
        int boundDigit = bound[position] - '0';

        for (int tight = 0; tight <= 1; ++tight) {
            int upper = tight ? boundDigit : 9;
            int lower = position == 0 ? 1 : 0;
            for (int remainder = 0; remainder < divisorMod; ++remainder) {
                int ways = dp[tight][remainder];
                if (ways == 0) continue;

                for (int digit = lower; digit <= upper; ++digit) {
                    bool evenPosition = (position + 1) % 2 == 0;
                    if (evenPosition && digit != magicDigit) continue;
                    if (!evenPosition && digit == magicDigit) continue;

                    int nextTight = tight && digit == boundDigit;
                    int nextRemainder = (remainder * 10 + digit) % divisorMod;
                    addModulo(next[nextTight][nextRemainder], ways);
                }
            }
        }
        dp.swap(next);
    }

    int result = dp[0][0];
    addModulo(result, dp[1][0]);
    return result;
}

bool isValid(const string& number) {
    int remainder = 0;
    for (int position = 0; position < static_cast<int>(number.size()); ++position) {
        int digit = number[position] - '0';
        bool evenPosition = (position + 1) % 2 == 0;
        if (evenPosition && digit != magicDigit) return false;
        if (!evenPosition && digit == magicDigit) return false;
        remainder = (remainder * 10 + digit) % divisorMod;
    }
    return remainder == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> divisorMod >> magicDigit;
    string lower, upper;
    cin >> lower >> upper;

    int answer = countUpTo(upper) - countUpTo(lower);
    if (answer < 0) answer += MOD;
    if (isValid(lower)) addModulo(answer, 1);
    cout << answer << '\n';
}

每一位、每个余数最多尝试 10 个数字，时间复杂度 O(length×m×10)，空间复杂度 O(m)。答案始终按 10^9+7 取模。

5. 第三题：55D Beautiful numbers

5.1 从“每个数字”压缩为一个 LCM

一个正整数若能被其十进制表示中的每个非零数字整除，就称为 beautiful number。数字 0 被忽略，因为除以 0 没有定义。

若已经出现的非零数字集合为 D，要求整数能被 D 中每个数整除，等价于整数能被它们的最小公倍数整除。于是无需保存出现过哪些数字，只保存：

1
lcmValue = lcm(所有已经出现的非零数字)

追加数字 0 时 LCM 不变；追加 digit>0 时更新为 lcm(lcmValue,digit)。

5.2 为什么余数只需模 2520

数字 1 到 9 的最小公倍数为：

1
lcm(1,2,...,9) = 2520

任意数字集合的 LCM 都是 2520 的约数。若最终需要判断 number % lcmValue == 0，保存 number % 2520 就足够，因为 lcmValue 一定整除 2520。

2520 的质因数分解为 2³×3²×5×7，约数个数为：

1
(3+1)(2+1)(1+1)(1+1) = 48

所以看似有 2521 种 LCM 数值，实际只有 48 个可达状态。把这些约数编号后，状态规模为：

1
remaining × 2520 × 48

5.3 把非紧状态预计算成“自由后缀”

由于最多 10 组区间，每次重新计算全部非紧状态很浪费。本文定义：

1
freeWays(remaining, remainder, lcmIndex)

表示前缀已经严格小于上界时，再自由填 remaining 位，最终满足整除条件的方案数。它与具体上界无关，可以在所有询问之间复用。

处理某个上界时，从左到右沿它的数字走。每一位先枚举比上界当前位小的数字，这些分支直接查 freeWays；随后选择恰好等于上界位的数字，继续保持贴边。这样既避免为每个上界建立一套 tight 记忆，也让预计算只发生一次。

5.4 状态演算

考虑前缀 12：

已读前缀 模 2520 余数 非零数字 LCM 最终要求
空 0 1 暂无额外限制
1 1 1 被 1 整除
12 12 2 被 2 整除
120 120 2 0 不改变 LCM
126 126 6 同时被 1、2、6 整除

12 是 beautiful，因为 12%2=0；13 不是，因为 LCM 为 3，而 13%3≠0。官方区间 [12,15] 中只有 12 与 15 合法，所以答案为 2。

5.5 正确性证明

对任意前缀，remainder 由十进制追加公式准确维护其模 2520 的值；lcmValue 准确等于所有已出现非零数字的最小公倍数。两项通过逐位归纳成立。

所有非零数字都整除 2520，因此 lcmValue 也是 2520 的约数。最终整数能被每个非零数字整除，当且仅当它能被 lcmValue 整除；保存的模 2520 余数对这个判断足够。

freeWays 枚举每个自由后缀的十进制位且每条后缀路径唯一。计算上界时，小于当前位的分支与继续贴边的分支互不相交，并覆盖所有不超过上界的整数。因此 F(x) 正确，区间差也正确。

5.6 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

constexpr int BASE = 2520;
constexpr int MAX_REMAINING = 18;
constexpr int LCM_STATES = 48;

long long memo[MAX_REMAINING + 1][BASE][LCM_STATES];
vector<int> divisors;
int indexByValue[BASE + 1];

long long freeWays(int remaining, int remainder, int lcmIndex) {
    long long& result = memo[remaining][remainder][lcmIndex];
    if (result != -1) return result;

    int lcmValue = divisors[lcmIndex];
    if (remaining == 0) return result = (remainder % lcmValue == 0);

    result = 0;
    for (int digit = 0; digit <= 9; ++digit) {
        int nextRemainder = (remainder * 10 + digit) % BASE;
        int nextLcm = digit == 0 ? lcmValue : lcm(lcmValue, digit);
        result += freeWays(remaining - 1, nextRemainder, indexByValue[nextLcm]);
    }
    return result;
}

long long countUpTo(long long bound) {
    string digits = to_string(bound);
    long long answer = 0;
    int remainder = 0;
    int lcmIndex = indexByValue[1];

    for (int position = 0; position < static_cast<int>(digits.size()); ++position) {
        int limit = digits[position] - '0';
        int remaining = static_cast<int>(digits.size()) - position - 1;
        int lcmValue = divisors[lcmIndex];

        for (int digit = 0; digit < limit; ++digit) {
            int nextRemainder = (remainder * 10 + digit) % BASE;
            int nextLcm = digit == 0 ? lcmValue : lcm(lcmValue, digit);
            answer += freeWays(remaining, nextRemainder, indexByValue[nextLcm]);
        }

        remainder = (remainder * 10 + limit) % BASE;
        int nextLcm = limit == 0 ? lcmValue : lcm(lcmValue, limit);
        lcmIndex = indexByValue[nextLcm];
    }

    if (remainder % divisors[lcmIndex] == 0) ++answer;
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int value = 1; value <= BASE; ++value) {
        if (BASE % value == 0) divisors.push_back(value);
    }
    for (int index = 0; index < static_cast<int>(divisors.size()); ++index) {
        indexByValue[divisors[index]] = index;
    }
    fill(&memo[0][0][0], &memo[0][0][0] + sizeof(memo) / sizeof(long long), -1LL);

    int tests;
    cin >> tests;
    while (tests--) {
        long long left, right;
        cin >> left >> right;
        cout << countUpTo(right) - countUpTo(left - 1) << '\n';
    }
}

可达自由状态至多约 19×2520×48 个，每个状态枚举 10 个数字；记忆结果在所有测试间复用。内存约 19 MB，区间端点和计数使用 long long。

6. 三题的状态为什么越来越多

题目 必要状态 不需要保存的内容 压缩依据
1036C 位置、非零位数、tight 已填前缀的具体数值 未来只关心是否超过 3 个非零位
628D 位置、模 m 余数、tight 最多 2000 位的完整前缀 整除性只取决于余数
55D 位置、模 2520 余数、LCM、tight 出现数字的集合与完整前缀 整除全部数字等价于整除其 LCM

状态越多不代表越好。状态设计的目标是保存所有会影响未来的区别，同时合并不再影响未来的历史。1036C 不必知道非零数字分别是什么；628D 不必知道前缀商；55D 不必保存九个布尔标记，因为 LCM 已经概括整除要求。

7. 边界与错误清单

场景 常见错误 正确处理
1036C 前导零 当作非零位或另建无用分支 数字 0 不增加 used
1036C L=1 不会处理 L-1=0 F(0) 合法定义，区间差自动抵消 0
tight 转移 用 digit==9 判断 必须与当前上界位比较，且旧状态仍为 tight
628D 奇偶位置 把代码下标偶数当数学偶数位 数学位置是 position+1
628D 数字 d 只要求偶数位等于 d 奇数位还必须不等于 d
628D 第一位 允许 0 上下界无前导零，只统计同长度正整数
628D 区间 对 2000 位 a 直接转整数 使用字符串上界和 F(b)-F(a)+valid(a)
55D 数字 0 把 LCM 更新为 0 0 不参与整除条件，LCM 保持不变
55D 保存余数 模当前 LCM LCM 会变化，应统一模 2520
55D LCM 状态 为 1 到 2520 全部分配有效状态 只会到达 48 个约数
55D 计数类型 使用 int 上界接近 9×10^18，必须使用 long long

8. 独立验证

tests/verify-digit-dp-three-article.cjs 会提取三段 C++17，以 -Wall -Wextra -pedantic 编译并要求零警告。参考方法尽量避开正文转移：

  • 1036C 独立生成所有至多含三个非零位的整数，排序后用二分统计区间；
  • 628D 在较短等长区间逐个检查位置规则与整除性；
  • 55D 在小范围逐个读取十进制数字并直接检查每个非零数字。

测试覆盖官方样例、随机区间、单点、数字 0 出现在不同位置、上下界相等、10^18、2000 位字符串，以及接近 9×10^18 的 64 位边界。第二题另用 2000 位、m=2000 的单点区间压测完整状态空间；第三题用最大量级单点检查预计算与计数不会溢出。

数位 DP 最容易写出“看起来像模板”的错误代码。每加一个状态，都应写清它区分了哪两类未来；每删除一个状态，也要证明被合并的历史对所有后缀拥有相同答案。