数位 DP：上界限制、前导零与记忆化搜索

当题目要求我们统计区间 $[L, R]$ 内，满足某种奇怪规律（比如不含数字 4、相邻数字相差 2）的数字个数，且 $R$ 高达 $10^{18}$ 时，普通 for 循环直接瘫痪。

数位 DP 的核心思想，就是把写数字的过程，变成“从高到低转密码锁”的过程，并利用记忆化把算过的结果存起来。不再枚举上限以内的每个数，而是枚举“数位 × 历史状态”，规模一下就降下来了。

一、区间转换（化繁为简）

我们要查 $[L, R]$ 区间，直接查很难，因为有两个边界。

通用降维法则（前缀和差分）：

设 $f(x)$ 表示从 $1 \dots x$ 里面有多少个合法的数字。

那么求 $[L, R]$ 的答案，直接转化为：f(R) - f(L-1)。

这样，我们永远只需要解决一个问题：“求不超过最大上限 $X$ 的合法数字个数”，下界永远固定，瞬间省去了一半的分类讨论。

数位 DP：区间前缀差分与上限

二、数位 DFS 的“黄金四参数”

想象你要填一个不超过 $324$ 的三位数字。我们有三个密码拨圈，从高位（百位）向低位（个位）填。

无论题目怎么变，我们写搜索函数 f 时，永远死死抱住这四个极简参数：f(p, pre, lim, zero)。

1. `p` (位置)

当前正在拨第几个密码圈。比如 324，拆成数组 a = [4, 2, 3]（从低到高存）。当前如果在百位，p = 3；全拨完了，p = 0。

2. `pre` (历史状态)

上一个拨圈填了什么数字。因为题目经常要求“相邻数字如何如何”，我们需要 pre 来做比较。如果是统计某个数字出现的次数，这里就换成 sum（目前为止出现了几次）。

3. `lim` (天花板限制：极其重要！)

这是学生最容易迷糊的地方。

我们要造的数字绝对不能超过 $324$ 。

贴着天花板 (lim = 1)：假设你百位拨了 3，那你十位能随便拨 $0 \dots 9$ 吗？绝对不行！十位最多只能拨到 2。这种处于限制状态下的情况，就是 lim = 1。
解除天花板 (lim = 0)：假设你百位拨了 1，那你十位可以随便拨 $0 \dots 9$ 吗？可以！因为就算你拨出 199，也绝对不会超过 $324$ 。只要限制解除了，后面的拨圈全部彻底自由！

4. `zero` (前导零)

数字 004 其实就是 4。但在密码锁上，我们前两个圈拨了 0。

前导零是虚无的，它不能算作真实的数字参与规则判定。

比如要求“相邻差大于 2”，前导零的 0 和后面的实数之间不需要判定差值。
如果是统计数字 0 出现的次数，前导零的 0 绝对不能算进去。

三、记忆化的绝对铁律

我们开一个二维数组 dp[p][pre] 存答案。

什么情况下的答案才能存进 dp 里复用？

本讲二维缓存的铁律：只有当 !lim && !zero 时才能存！

如果不受天花板限制（!lim），且前面已经有真实数字了（!zero），那么剩下几个拨圈的合法组合数是一个普适的定值。
被 lim 限制的路线是特例（只有一条），不能存。带有前导零的路线也是特例，不能和普通路线混淆。

数位 DP：黄金四参数与记忆化铁律

四、核心模型一：相邻数位约束 (Windy 数)

场景：求区间内相邻数字差的绝对值 $\ge 2$ 的数字个数。（洛谷 P2657）

代码推演：

如果当前是前导零 (zero=1)，那之前拨的数字根本不存在，当前这步不需要算绝对值差。

只有当 zero=0 且 abs(i - pre) >= 2 时，才能正常往下拨。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int dp[N][N],a[N];

// p:当前位, pre:上一位数字, lim:是否有上限, zero:是否为前导零
int f(int p,int pre,int lim,int zero){
    if(p==0) return !zero; // 本题只数正整数，整条路线都是前导零时不计入
    if(!lim && !zero && dp[p][pre]!=-1) return dp[p][pre];
    
    int ans=0,up=lim?a[p]:9; // 确定当前位能枚举到的最大数字
    
    for(int i=0;i<=up;i++){
        if(zero){
            // 还在前导零状态，随便填，下一位的 zero 取决于当前位是不是继续填 0
            ans+=f(p-1,i,lim&&(i==up),i==0);
        }else if(abs(i-pre)>=2){
            // 脱离前导零，必须满足题目差值条件
            ans+=f(p-1,i,lim&&(i==up),0);
        }
    }
    
    if(!lim && !zero) dp[p][pre]=ans; // 满足铁律，存入记忆化数组
    return ans;
}

int calc(int x){
    if(x<=0) return 0;
    int len=0;
    while(x){
        a[++len]=x%10;
        x/=10;
    }
    // 初始从最高位开始，上一位随便给个 -2 避免冲突，处于限制中，处于前导零中
    return f(len,-2,1,1);
}

void solve(){
    memset(dp,-1,sizeof dp); // 多次查询只用清空一次，因为 dp 存的是普适无限制状态
    int l,r;
    cin>>l>>r;
    cout<<calc(r)-calc(l-1)<<"\n";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

Windy 数：相邻数位差的绝对值至少为 2

五、核心模型二：特定数码统计 (数字计数)

场景：求区间内每个数码（ $0 \sim 9$ ）各出现了多少次。（洛谷 P2602）

代码推演：

这里我们不再关心“上一位是多少”，我们只关心“目标数码 tar 已经出现了多少次”。所以 pre 换成了 sum。

避坑核心：当统计数码 0 时，如果当前处于前导零状态，这个 0 绝对不能让 sum 加一。必须写成 !(zero && i==0) 来屏蔽。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int dp[N][N],a[N];

// sum:目标数码出现的次数, tar:当前要统计的目标数码
int f(int p,int sum,int lim,int zero,int tar){
    if(p==0) return sum;
    if(!lim && !zero && dp[p][sum]!=-1) return dp[p][sum];
    
    int ans=0,up=lim?a[p]:9;
    
    for(int i=0;i<=up;i++){
        int nsum=sum;
        // 如果填入的正好是目标数码，且不能是虚假的前导零，次数才增加
        if(!(zero && i==0) && i==tar){
            nsum++;
        }
        ans+=f(p-1,nsum,lim&&(i==up),zero&&(i==0),tar);
    }
    
    if(!lim && !zero) dp[p][sum]=ans;
    return ans;
}

int calc(int x,int tar){
    if(x<=0) return 0; // calc(x,tar) 只统计 1..x，不包含数字 0 本身
    int len=0;
    while(x){
        a[++len]=x%10;
        x/=10;
    }
    memset(dp,-1,sizeof dp); // 每次换目标数字统计，dp 必须清空
    return f(len,0,1,1,tar);
}

void solve(){
    int l,r;
    cin>>l>>r;
    for(int i=0;i<=9;i++){
        cout<<calc(r,i)-calc(l-1,i)<<(i==9?"":" ");
    }
    cout<<"\n";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

数字计数：统计 tar 出现次数与前导零

六、进阶技巧：多测调用与缓存的独立性

在刚才的“Windy 数”和“数字计数”两份代码中，你可能注意到一个细节：

Windy 数的 memset(dp, -1) 写在 solve() 里，本次区间查询的 calc(r) 与 calc(l-1) 共用缓存。若要处理多组询问，可以把初始化移到循环外复用，也可以每组重新初始化。
数字计数的 memset 却写在 calc() 里，每次换目标数字 tar 都要重新清空。

为什么？缓存到底依赖什么？ 记住，我们存进 dp 数组里的，是 !lim && !zero（完全自由）状态下的答案。这个答案与上界 R 毫无关系。所以，就算有多个不同上界的询问，只要判断合法性的规则不变，缓存就可以一直复用。

但在数字计数中，我们的目标数字 tar 在外层循环变化。当 tar = 2 时，dp[3][1] 表示“剩下 3 位，数字 2 已经出现 1 次”时，后面所有自由填法累计得到的出现总次数；当 tar = 5 时，统计对象就换成了数字 5。写模板时，每换一个 tar 就清空一次缓存，不把不同统计对象的结果混用。

实战原则：如果题目的附加条件（如目标数字、模数）改变了，且这个条件没有作为维度写进 dp 数组里，就必须重新 memset。

七、核心模型三：余数维度的拼接与转移（选学）

场景：求区间内能被自身数位和整除的数字个数。（对应洛谷 P4127） 先修要求：熟练掌握上述四参数模板。

判断整除，核心是记录“余数”。但我们在拨密码锁时是从高往低拨的，余数该怎么算？ 手推一下：假设要判断数字 324 能不能被 7 整除。

先看百位 3： $3 \bmod 7 = 3$ 。
再看十位 2：把上一位的余数乘 10，加上当前位， $(3 \times 10 + 2) \bmod 7 = 32 \bmod 7 = 4$ 。
最后看个位 4： $(4 \times 10 + 4) \bmod 7 = 44 \bmod 7 = 2$ 。最终余数不为 0，说明不能整除。

规律非常清晰：新余数 = (老余数 * 10 + 当前填的数) % mod。在这道题中，目标模数 mod 就是数字的数位和。由于最终的数位和在没填完之前是未知的，我们可以外层循环枚举所有可能的数位和（18位数字最大数位和为 $18 \times 9 = 162$ ），然后在 DFS 中同时记录“当前已经累加的数位和 sum”以及“当前的余数 rem”。

// 输入格式: L R (1 <= L <= R <= 10^18)
// 输出格式: 区间内满足“能被自身数位和整除”的数字个数
// 样例输入: 10 19
// 样例输出: 3 (样例解释：10, 12, 18 能被自身数位和整除)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20, M=165;
int dp[N][M][M], a[N];
int mod; // 当前枚举的数位和目标

int f(int p, int sum, int rem, int lim, int zero){
    if(sum > mod) return 0; // 剪枝：已经超过目标数位和，直接废弃
    if(p == 0) return (sum == mod && rem == 0) ? 1 : 0;
    if(!lim && !zero && dp[p][sum][rem] != -1) return dp[p][sum][rem];
    
    int ans = 0, up = lim ? a[p] : 9;
    for(int i = 0; i <= up; i++){
        // 余数公式：(老余数 * 10 + i) % mod
        ans += f(p - 1, sum + i, (rem * 10 + i) % mod, lim && (i == up), zero && (i == 0));
    }
    
    if(!lim && !zero) dp[p][sum][rem] = ans;
    return ans;
}

int calc(int x){
    if(x <= 0) return 0;
    int len = 0;
    while(x){
        a[++len] = x % 10;
        x /= 10;
    }
    int total = 0;
    // 枚举数位和作为模数，18位数最大数位和为 162
    for(mod = 1; mod <= 162; mod++){
        memset(dp, -1, sizeof dp); // 每次 mod 改变，规则变了，缓存必须清空
        total += f(len, 0, 0, 1, 1);
    }
    return total;
}

void solve(){
    int l, r;
    cin >> l >> r;
    cout << calc(r) - calc(l - 1) << "\n";
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

八、核心模型四：打包返回方案数与属性和（选学）

场景：求区间内所有数字的数位和相加的结果。（对应洛谷 P4999）

如果你遇到这类求“所有合法状态的数值和/数位和”的题目，你可能会想：能不能把前面的累加值当参数传下去？可以，但缓存维度会急剧膨胀（如变为 dp[p][sum]）。如果题目要求的是“原数字的真实数值之和”，数值大到根本无法作为数组下标！

第九节题单中累计数位和的二维状态同样能做。这里换一种省状态的写法：用结构体打包返回方案数和数位和。痛点：如果你 DFS 只传回一个“总和”，到了上一层，你根本不知道这个总和是几个数字产生的，也就无法计算当前层选的数字该贡献多少！

举个具体例子：假设你在百位填了 3。通过询问后续状态，得知后面有 5 种合法的填法，并且这 5 种填法本身产生的数位和一共是 40。那么百位的 3 该算几次？因为被这 5 种方案共用了，所以 3 必须被加 5 次。这一层汇总的总和应该是：后方总和 (40) + 当前数字 (3) * 合法方案数 (5) = 55。

核心逻辑：必须同时传回“合法后缀的方案数 cnt”和“这些后缀产生的总和 sum”。

下面保留单组 L R 的教学实现。提交 P4999 时，原题先读询问组数 T：在 main 中将单次 solve(); 改为 int T; cin>>T; while(T--) solve();。solve 内每组初始化这 20 格缓存完全可用；若想复用缓存，再把初始化移到循环外即可。

// 输入格式: L R (1 <= L <= R <= 10^18)
// 输出格式: 区间内所有数字的数位和相加的结果，对 10^9+7 取模
// 样例输入: 10 19
// 样例输出: 55
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 20, MOD = 1e9+7;
int a[N];

// 打包结构体
struct Node {
    int cnt; // 有多少个合法的后缀
    int sum; // 这些后缀贡献的数位和
};

Node dp[N]; // 这个状态完全自由，只需要记当前到了第几位

Node f(int p, int lim, int zero){
    if(p == 0) return {1, 0}; // 到了终点，找到 1 种方案，后缀初始和为 0
    if(!lim && !zero && dp[p].cnt != -1) return dp[p];
    
    Node ans = {0, 0};
    int up = lim ? a[p] : 9;
    
    for(int i = 0; i <= up; i++){
        Node sub = f(p - 1, lim && (i == up), zero && (i == 0));
        // 1. 方案数直接累加
        ans.cnt = (ans.cnt + sub.cnt) % MOD;
        // 2. 重点：当前数字 i 被 sub.cnt 个后缀共用了！
        int cur_digit_sum = (i * sub.cnt) % MOD;
        ans.sum = (ans.sum + sub.sum + cur_digit_sum) % MOD;
    }
    
    if(!lim && !zero) dp[p] = ans;
    return ans;
}

int calc(int x){
    if(x <= 0) return 0;
    int len = 0;
    while(x){
        a[++len] = x % 10;
        x /= 10;
    }
    return f(len, 1, 1).sum;
}

void solve(){
    // 规则没有任何附加限制，多次查询只需要在最开始初始化一次
    for(int i = 0; i < N; i++) dp[i].cnt = -1; 
    int l, r;
    cin >> l >> r;
    cout << (calc(r) - calc(l - 1) + MOD) % MOD << "\n";
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

九、渐进式实战练习题单

洛谷 P2657 [SCOI2009] windy 数
- 训练指引：基础入门题。强制用四参数模板完成，深刻理解前导零 zero 是如何让第一个数字的选取变得自由的。
洛谷 P2602 [ZJOI2010] 数字计数
- 训练指引：统计计数的标杆。重点突破 !(zero && i==0) 这一行防线，彻底吃透前导零对于数字 0 的特殊干扰。
洛谷 P4999 烦人的数学作业
- 训练指引：求区间所有数字的数位之和。可以直接用第八节打包返回 cnt/sum 的写法，也可以把第五节的 sum 从“目标数码出现次数”改为“已经填入的数位和”，每填一位就加上 i。若采用后一种写法，缓存也要一起扩容：19 位数的数位和最多是 $19\times9=171$ ，可开 dp[20][200]，不能继续用 dp[20][20]。搜索累加时对 mod=1000000007 取模，最后用 (calc(r)-calc(l-1)+mod)%mod 处理区间差。两种写法提交原题时都要先读 T，逐组处理 L R。
洛谷 P4127 [AHOI2009] 同类分布
- 训练指引：求数位和能整除原数的数。先枚举最终数位和 s，再用数位 DP 同时记录当前数位和与对 s 的余数，添加数码 i 时，余数变成 (rem*10+i)%s。不同 s 的缓存不能混用。先遮住第七节代码自己写一遍，再对照检查这两个状态。

数位 DP