OI-wiki 数位 DP 完全指南原理、模板与五道经典例题实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读数位 DPDigit DP是动态规划家族中专门用于解决「统计区间内满足某类数位约束条件的数字个数」问题的经典技巧。本文以 OI-wiki 动态规划章节的 数位 DP 页面 为骨架系统讲解数位 DP 的识别特征、基本原理与两种主流实现范式循环递推与记忆化搜索并完整展开 5 道由浅入深的经典例题从最朴素的数码计数Luogu P2602、禁止型约束HDU 2089「不要 62」、相邻位差约束SCOI2009 windy 数到大整数与镜像约束SPOJ MYQ10再到与 AC 自动机结合的字符串多模匹配Luogu P3311。读完本文你将能够独立识别数位 DP 题目、设计状态与转移方程并将文中模板迁移到自己的题目中。什么是数位 DP数位从「数」到「串」的视角转换数位是指把一个数字按照个、十、百、千……一位一位地拆开关注它每一位上的数字。如果拆的是十进制数那么每一位数字都是 $0\sim 9$其他进制可以类比十进制理解。把一个整数看成「数位组成的序列」正是数位 DP 一切工作的前提。数位 DP 的四个识别特征根据 OI-wiki 的总结数位 DP 解决的问题「比较好辨认」一般具有以下四个特征要求统计满足一定条件的数的数量即最终目的为计数这些条件经过转化后可以使用「数位」的思想去理解和判断输入会提供一个数字区间有时也只提供上界作为统计的限制上界很大比如 $10^{18}$暴力枚举验证会超时。第 4 点最关键例如当上界达到 $10^{18}$ 量级时逐个数枚举的时间复杂度是不可接受的必须利用数位结构上的重复性来压缩计算。基本原理归并重复计数过程考虑人类计数的方式最朴素的计数就是从小到大依次加一。但对于位数比较多的数这个过程中存在大量重复的部分。例如从 7000 数到 7999、从 8000 数到 8999、从 9000 数到 9999 的过程非常相似它们都是后三位从 000 变到 999不一样的只有千位这一位。数位 DP 的核心思想就是把这些相似的过程归并起来将这些过程中产生的计数答案都存放在一个通用的数组里。这个数组根据题目具体要求设置状态用递推或 DP 的方式进行状态转移从而把「数 $10^{18}$ 个数」压缩为「处理 $18 \times 10$ 种数位状态」。区间减法化区间为前缀数位 DP 中通常会利用常规计数问题技巧——前缀差分把区间答案拆成两部分相减$$ \mathit{ans}{[l, r]} \mathit{ans}{[0, r]} - \mathit{ans}_{[0, l-1]} $$这样任意区间统计问题都转化为「统计 $[0, n]$ 内满足条件的数字个数」这一更简单的问题例题三中则使用 $\mathit{ans}_{[1, i]}$ 的约定本质相同。有了通用答案数组之后统计答案有两种方式记忆化搜索或循环迭代递推。为了不重不漏地统计所有不超过上限的答案要从高到低枚举每一位再考虑每一位可以填哪些数字最后利用通用答案数组统计答案。补充阅读数位 DP 与 动态规划基础、记忆化搜索 一脉相承也与 计数 DP 关系密切——计数 DP 强调「将集合划分为无交子集再求和」的计数思想数位 DP 正是这一思想在数位维度上的具体应用。在 OI-wiki 的文档体系中数位 DP 被编排在动态规划章节的「数位 DP」条目下见 mkdocs.yml 中dp/number.md的导航配置。例题一数码计数Luogu P2602 数字计数题目给定两个正整数 $a,b$求在 $[a,b]$ 中的所有整数中每个数码digit各出现了多少次。这是数位 DP 的入门经典题OI-wiki 给出了**方法一循环递推和方法二记忆化搜索**两种实现恰好覆盖了数位 DP 的两大实现范式。方法一递推 按位统计解释发现对于满 $i$ 位的数所有数字出现的次数都是相同的故设数组 $dp_i$ 为满 $i$ 位的数中每个数字出现的次数此时暂时不处理前导零。则有$$ dp_i 10 \times dp_{i-1} 10^{i-1} $$其中两部分分别是前 $i-1$ 位数字的贡献每一轮高位的数字组合会把低位的所有次数重复 10 遍以及第 $i$ 位数字本身的贡献满 $i$ 位时第 $i$ 位每一位数字出现 $10^{i-1}$ 次。有了 $dp$ 数组统计答案时将上界按位分开从高到低枚举不贴着上界时后面可以随便取值直接乘上 $dp$ 数组即可贴着上界时后面只能取 $0$ 到上界的部分需分两部分分别计算贡献。最后还要处理前导零第 $i$ 位为前导 $0$ 时此时第 $1$ 到 $i-1$ 位也都是 $0$也就是多算了将 $i-1$ 位填满的答案需要额外减去。实现#include cstdio using namespace std; constexpr int N 15; using ll long long; ll l, r, dp[N], mi[N]; ll ans1[N], ans2[N]; int a[N]; void solve(ll n, ll *ans) { ll tmp n; int len 0; while (n) a[len] n % 10, n / 10; for (int i len; i 1; --i) { for (int j 0; j 10; j) ans[j] dp[i - 1] * a[i]; for (int j 0; j a[i]; j) ans[j] mi[i - 1]; tmp - mi[i - 1] * a[i], ans[a[i]] tmp 1; ans[0] - mi[i - 1]; } } int main() { scanf(%lld%lld, l, r); mi[0] 1ll; for (int i 1; i 13; i) { dp[i] dp[i - 1] * 10 mi[i - 1]; mi[i] 10ll * mi[i - 1]; } solve(r, ans1), solve(l - 1, ans2); for (int i 0; i 10; i) printf(%lld , ans1[i] - ans2[i]); return 0; }代码要点mi[i]预处理 $10^i$ 的幂用于计算「某一位固定后低位共有多少种取法」dp[i]由上面的递推式预处理solve(n, ans)统计 $[0, n]$ 内各数码出现次数主函数中通过solve(r) - solve(l-1)完成前缀差分每次按位处理时tmp - mi[i-1] * a[i]维护「当前位贴住上界时低位剩余的取值个数」从而对ans[a[i]]精确累加。方法二记忆化搜索解释此题也可以用记忆化搜索。$dp_i$ 表示不贴上限、无前导零时位数为 $i$ 的答案。关键参数有三个u当前处理的位数从高位向低位f0是否有前导零lim当前前缀是否全程贴着上限。记忆化的前提是状态完全脱离上下界限制只有!lim !f0时的搜索结果才能存入f[u]供后续复用这是数位 DP 记忆化搜索的通用原则。实现#include cstdio #include cstring #include iostream using namespace std; using ll long long; constexpr int N 50005; ll a, b; ll f[15], ksm[15], p[15], now[15]; ll dfs(int u, int x, bool f0, bool lim) { // u 表示位数f0 是否有前导零lim 是否都贴在上限上 if (!u) { if (f0) f0 false; return 0; } if (!lim !f0 (~f[u])) return f[u]; ll cnt 0; int lst lim ? p[u] : 9; for (int i 0; i lst; i) { // 枚举这位要填的数字 if (f0 i 0) cnt dfs(u - 1, x, 1, lim i lst); // 处理前导零 else if (i x lim i lst) cnt now[u - 1] 1 dfs(u - 1, x, 0, lim i lst); // 此时枚举的前几位都贴在给定的上限上 else if (i x) cnt ksm[u - 1] dfs(u - 1, x, 0, lim i lst); else cnt dfs(u - 1, x, 0, lim i lst); } if ((!lim) (!f0)) f[u] cnt; // 只有不贴着上限和没有前导零才能记忆 return cnt; } ll gans(ll d, int dig) { int len 0; memset(f, -1, sizeof(f)); while (d) { p[len] d % 10; d / 10; now[len] now[len - 1] p[len] * ksm[len - 1]; } return dfs(len, dig, 1, 1); } int main() { scanf(%lld%lld, a, b); ksm[0] 1; for (int i 1; i 12; i) ksm[i] ksm[i - 1] * 10ll; for (int i 0; i 9; i) printf(%lld , gans(b, i) - gans(a - 1, i)); printf(%lld\n, gans(b, 9) - gans(a - 1, 9)); return 0; }代码要点gans(d, dig)把上界d拆成数位存入p[]同时用now[]前缀数组维护「贴着上界时该位之后剩余的可取值个数」now[len] now[len-1] p[len] * ksm[len-1]供贴界转移时直接取用dfs(u, x, f0, lim)对数码x单独统计贴界且当前位等于x时贡献为now[u-1] 1贴住的部分全部计入再递归不贴界且当前位等于x时贡献为ksm[u-1]低位任意取值中x出现 $10^{u-1}$ 次再递归主函数对每个数码分别调用gans最后做区间差分。关于记忆化搜索的更多细节记忆数组的初始化、为什么每个状态只访问一次、与递推的异同可进一步阅读 OI-wiki 的 记忆化搜索 页面其中以「采药」问题为例说明了记忆化的三步骤写法。例题二禁止型约束HDU 2089 不要 62题面大意统计一个区间内数位上不能有 4 也不能有连续的 62 的数有多少。解释这道题引入了数位 DP 中非常典型的「状态压缩约束信息」思路约束一不含 4在枚举的时候判断一下不枚举 4 就可以保证状态合法。这个约束只与当前位有关因此没有记忆化的必要——它不是跨位约束约束二不含连续 62涉及两位当前一位是 6 或者不是 6 这两种不同情况计数是不相同的所以要用状态记录不同的方案数。设 $dp_{pos, sta}$ 表示当前第 $pos$ 位、前一位是否是 6 的状态这里 $sta$ 只需要取 0 和 1 两种状态不是 6 的情况可视为同种不会影响计数。同时额外使用 $sta2$ 表示「已经出现非法数含 4 或 62」用于递推。实现#include cstdio #include cstring #include iostream using namespace std; int x, y, dp[15][3], p[50]; void pre() { memset(dp, 0, sizeof(dp)); dp[0][0] 1; for (int i 1; i 10; i) { dp[i][0] dp[i - 1][0] * 9 - dp[i - 1][1]; dp[i][1] dp[i - 1][0]; dp[i][2] dp[i - 1][2] * 10 dp[i - 1][1] dp[i - 1][0]; } } int cal(int x) { int cnt 0, ans 0, tmp x; while (x) { p[cnt] x % 10; x / 10; } bool flag false; p[cnt 1] 0; for (int i cnt; i; i--) { // 从高到低枚举数位 ans p[i] * dp[i - 1][2]; if (flag) ans p[i] * dp[i - 1][0]; else { if (p[i] 4) ans dp[i - 1][0]; if (p[i] 6) ans dp[i - 1][1]; if (p[i] 2 p[i 1] 6) ans dp[i][1]; if (p[i] 4 || (p[i] 2 p[i 1] 6)) flag true; } } return tmp - ans; } int main() { pre(); while (~scanf(%d%d, x, y)) { if (!x !y) break; if (x y) swap(x, y); printf(%d\n, cal(y 1) - cal(x)); } return 0; }代码要点pre()递推三个状态dp[i][0]表示前一位非 6 的合法数个数dp[i][1]表示前一位是 6 的合法数个数dp[i][2]表示已经非法的数个数cal(x)统计 $[0, x]$ 内的非法数个数再用tmp - ans得到合法数个数。从高到低按位累加「贴界时小于当前位的分支」贡献并用flag标记前缀是否已经非法主函数中cal(y 1) - cal(x)的写法把区间 $[x, y]$ 转化为两个前缀差同时利用(0, 0)作为输入终止标记题目约定。这一「用额外状态维度记录跨位约束」的手法在数位 DP 中极为常见windy 数、镜像回文数等题目都是它的变体。例题三相邻位差约束SCOI2009 windy 数题目给定一个区间 $[l,r]$求其中满足条件不含前导 $0$ 且相邻两个数字相差至少为 $2$的数字个数。解释首先将问题转化成更简单的形式。设 $ans_i$ 表示在区间 $[1,i]$ 中满足条件的数的数量则所求答案为 $ans_r - ans_{l-1}$。关键观察对于一个小于 $n$ 的数它从高到低肯定出现某一位使得这一位上的数值小于 $n$ 这一位上对应的数值而之前的所有位都和 $n$ 上的位相等。因此可以定义$$ f(i, st, op) $$表示当前将要考虑的是从高到低的第 $i$ 位当前该前缀的状态为 $st$且前缀和当前求解数字的大小关系是 $op$$op1$ 表示等于$op0$ 表示小于时的数字个数。在本题中前缀状态 $st$ 就是上一位的值因为当前将要确定的位不能取哪些数只和上一位有关。OI-wiki 特别指出在其他题目中这个状态值可以是——前缀的数字和前缀所有数字的 $\gcd$该前缀取模某个数的余数也有两种或多种合用的情况。这说明「$st$ 具体记录什么」完全取决于题目约束的跨位依赖关系这是数位 DP 状态设计的灵魂。写出状态转移方程$$ f(i, st, op) \sum_{k1}^{maxx} f(i1, k, op1 \operatorname{and} kmaxx) \quad (|st - k| \ge 2) $$这里的 $k$ 是当前枚举的下一位的值$maxx$ 是当前能取到的最高位。因为如果 $op1$贴着上界那么这一位取的值一定不能大于求解数字上该位的值否则没有限制。可以发现尽管前缀选择的状态不同但只要 $f$ 的三个参数相同答案就是一样的。为防止这个答案被重复计算多次可以使用记忆化搜索实现——这与例题一中「只有不贴上限、无前导零才能记忆」的原则一致状态必须脱离上下界信息才有复用价值。实现int dfs(int x, int st, int op) // op1 ; op0 { if (!x) return 1; if (!op ~f[x][st]) return f[x][st]; int maxx op ? dim[x] : 9, ret 0; for (int i 0; i maxx; i) { if (abs(st - i) 2) continue; if (st 11 i 0) ret dfs(x - 1, 11, op (i maxx)); else ret dfs(x - 1, i, op (i maxx)); } if (!op) f[x][st] ret; return ret; } int solve(int x) { memset(f, -1, sizeof f); dim.clear(); dim.push_back(-1); int t x; while (x) { dim.push_back(x % 10); x / 10; } return dfs(dim.size() - 1, 11, 1); }代码要点用st 11作为「哨兵状态」表示还没有任何有效数字即前导零阶段此时填0仍停留在哨兵状态保证不含前导 0的要求abs(11 - 0) 2恒成立而0与后续真实数字的比较不会误伤前导零op (i maxx)是贴界标记的传递只有当前位取满maxx且此前已贴界下一层才继续贴界if (!op) f[x][st] ret;只记忆化不贴界的状态这与if (!op ~f[x][st])的复用判断严格对应。例题四镜像回文数SPOJ MYQ10题面假如手写下 $[n,m]$ 之间所有整数有多少数看起来和在镜子里看起来一模一样$n, m 10^{44},\ T 10^5$解释本题带来了两个新挑战大整数与镜像约束。首先明确「一模一样」的含义由于这里考虑的镜像只有 $0,1,8$ 的镜像是自己本身所以「一模一样」并不是传统意义上的回文串而是只含有 $0,1,8$ 的回文串。因此在数位 DP 过程中显然只有 $0,1,8$ 能被选中。其次由于数值超过 long long 范围$[n,m] [1,m] - [1,n-1]$ 不再适用高精度比较繁琐需要改为对 $n$ 是否合法单独判断$$ [n,m] [1,m] - [1,n] \mathrm{check}(n) $$镜像问题解决后如何判断回文需要用一个小数组b[]记录之前的值在未超过一半的长度时只要不超上限即可随便填在超过一半的长度时还需要判断当前位是否和与之「镜面对称」的位相等即b[now] b[eff - now 1]。OI-wiki 特别提醒一个性能陷阱这道题的记忆化部分不能用memset整体清零否则会导致超时——因为本题状态含eff有效位、ful0是否全为前导 0等多个维度且 $T$ 可达 $10^5$每组数据全量 memset 的代价不可接受。实现int check(char cc[]) { // n 的特判 int strc strlen(cc); for (int i 0; i strc; i) { if (!(cc[i] cc[strc - i - 1] (cc[i] 1 || cc[i] 8 || cc[i] 0))) return 0ll; } return 1ll; } // now: 当前位, eff: 有效位, fulc: 是否全顶格, ful0: 是否全0 int dfs(int now, int eff, bool ful0, bool fulc) { if (now 0) return 1ll; if (!fulc f[now][eff][ful0] ! -1) // 记忆化 return f[now][eff][ful0]; int res 0, maxk fulc ? dig[now] : 9; for (int i 0; i maxk; i) { if (i ! 0 i ! 1 i ! 8) continue; b[now] i; if (ful0 i 0) // 全前导 0 res dfs(now - 1, eff - 1, 1, 0); else if (now eff / 2) // 未过半程 res dfs(now - 1, eff, 0, fulc (dig[now] i)); // 已过半程 else if (b[now] b[eff - now 1]) res dfs(now - 1, eff, 0, fulc (dig[now] i)); } if (!fulc) f[now][eff][ful0] res; return res; } char cc1[100], cc2[100]; int strc, ansm, ansn; int get(char cc[]) { // 处理封装 strc strlen(cc); for (int i 0; i strc; i) dig[strc - i] cc[i] - 0; return dfs(strc, strc, 1, 1); } scanf(%s%s, cc1, cc2); printf(%lld\n, get(cc2) - get(cc1) check(cc1));代码要点check(cc)单独判定下界n本身是否合法从而支持[n,m] [1,m] - [1,n] check(n)的大整数区间统计dfs(now, eff, ful0, fulc)中eff表示有效位数用于计算镜面对称位置ful0区分「全前导 0」此时填 0 合法但不产生有效位fulc表示是否全程贴着上界超过半程后每填一位都要与对称位b[eff - now 1]比较实现回文校验记忆化状态f[now][eff][ful0]只在!fulc时存取且不依赖memset全量清零。例题五数位 DP 与 AC 自动机Luogu P3311 数数题面我们称一个正整数 $x$ 是幸运数当且仅当它的十进制表示中不包含数字串集合 $S$ 中任意一个元素作为其子串。例如当 $S {22, 333, 0233}$ 时$233233$ 是幸运数而 $23332333$、$2023320233$、$32233223$ 不是幸运数。给定 $n$ 和 $S$计算不大于 $n$ 的幸运数个数答案对 $10^97$ 取模。数据范围$1 \le n 10^{1201}$$1 \le m \le 100$$1 \le \sum_{i1}^m |s_i| \le 1500$$\min_{i1}^m |s_i| \ge 1$其中 $|s_i|$ 表示字符串 $s_i$ 的长度。$n$ 没有前导 0但 $s_i$ 可能有前导 0。解释阅读题面发现如果将数字看成字符串这就是一个多模匹配问题自然而然想到 AC 自动机。普通数位 DP 中先从高到低枚举数位再枚举每一位都填什么在这道题中自然转化为枚举已经填好的位数 $i$枚举此时停在 AC 自动机上的哪个节点 $j$从当前节点转移到它在 AC 自动机上的子节点。设 $f(i, j, 0/1)$ 表示当前从高到低已经填了 $i$ 位即在 AC 自动机上走过了 $i$ 条边此时停在标号为 $j$ 的节点上当前是否正好贴着上界。至于「不包含」条件只需在 AC 自动机上给每个模式串的结尾节点都打上标记DP 过程中一旦遇上这些结尾节点就跳过即可。转移很好想详见代码主函数部分。这道题把数位 DP 的「逐位枚举填什么数字」和 AC 自动机的「串上状态转移」完美统一填数字 $k$ 等价于沿 AC 自动机的字符边 $k$ 走一步多模匹配的「禁止子串」被编码为不可进入的节点集合。此题可以很好地帮助理解数位 DP 的原理——它展示了数位 DP 的状态可以携带任意复杂的自动机信息。实现#include cstdio #include cstring #include queue using namespace std; using ll long long; constexpr int N 1505; constexpr int mod 1000000007; int n, m; char s[N], c[N]; int ch[N][10], fail[N], ed[N], tot, len; void insert() { int now 0; int L strlen(s); for (int i 0; i L; i) { if (!ch[now][s[i] - 0]) ch[now][s[i] - 0] tot; now ch[now][s[i] - 0]; } ed[now] 1; } queueint q; void build() { for (int i 0; i 10; i) if (ch[0][i]) q.push(ch[0][i]); while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i 10; i) { if (ch[u][i]) { fail[ch[u][i]] ch[fail[u]][i], q.push(ch[u][i]), ed[ch[u][i]] | ed[fail[ch[u][i]]]; } else ch[u][i] ch[fail[u]][i]; } } ch[0][0] 0; } ll f[N][N][2], ans; void add(ll x, ll y) { x (x y) % mod; } int main() { scanf(%s, c); n strlen(c); scanf(%d, m); for (int i 1; i m; i) scanf(%s, s), insert(); build(); f[0][0][1] 1; for (int i 0; i n; i) { for (int j 0; j tot; j) { if (ed[j]) continue; for (int k 0; k 10; k) { if (ed[ch[j][k]]) continue; add(f[i 1][ch[j][k]][0], f[i][j][0]); if (k c[i] - 0) add(f[i 1][ch[j][k]][0], f[i][j][1]); if (k c[i] - 0) add(f[i 1][ch[j][k]][1], f[i][j][1]); } } } for (int j 0; j tot; j) { if (ed[j]) continue; add(ans, f[n][j][0]); add(ans, f[n][j][1]); } printf(%lld\n, ans - 1); return 0; }代码要点insert()把每个模式串插入 AC 自动机并在结尾节点打上ed标记build()用 BFS 构建fail指针并把fail链上的非法标记通过ed[ch[u][i]] | ed[fail[ch[u][i]]]向上传递子串包含关系主函数三层循环外层枚举已填位数 $i$中层枚举当前节点 $j$跳过ed[j]的非法节点内层枚举填的数字 $k$跳过转移目标ch[j][k]非法的分支第三维记录是否贴界不贴界状态直接转移贴界状态中若k c[i]转入不贴界若k c[i]保持贴界从而精确保证「不大于 $n$」最终答案对 $10^97$ 取模并减去1排除全 0 的数字 0因为幸运数要求是正整数。习题消化完五道例题后可通过以下题目巩固数位 DP 的各种变形Ahoi2009 self 同类分布状态携带数字和且需同时枚举模数洛谷 P3413 SAC#1 - 萌数回文类约束HDU 6148 Valley Number数位升降趋势约束多状态记录CF55D Beautiful numbers约束依赖整个前缀的模数信息需用 $\operatorname{lcm}$ 压缩状态CF628D Magic Numbers奇偶位约束 取模其中 CF55D 与 P4127 都体现了例题三中提到的「状态可以是前缀数字和、前缀 $\gcd$、前缀取模余数等」的推广思想是检验状态设计能力的绝佳素材。总结数位 DP 的通用方法论综合 OI-wiki 数位 DP 页面与以上五道例题可以提炼出数位 DP 的通用解题流程识别题目计数目标 数位可描述约束 区间/上界输入 上界极大超过 $10^9$ 即应考虑区间转前缀利用 $ans_{[l,r]} ans_{[0,r]} - ans_{[0,l-1]}$大整数场景改用 $check$ 补差设计状态从高到低逐位填数状态至少包含「当前位」与「是否贴界」再根据约束的跨位依赖补充维度前一位的值、前缀和/$\gcd$/余数、是否已有前导零、AC 自动机节点等选择实现记忆化搜索实现直观、边界好处理循环递推便于按位统计与精确控制两者时间复杂度相同但递推可避开递归栈开销与memset性能问题如例题四只记忆化「自由」状态凡是受上下界或前导零影响的状态分支都不能写入记忆数组否则会污染复用结果。数位 DP 是 OI/ICPC 计数问题中的高频考点掌握本文的递推与记忆化两种模板、理解「状态压缩跨位约束」的本质即可从容应对从入门到 AC 自动机结合级别的各类变体。如需进一步补充动态规划理论背景可继续阅读 OI-wiki 的 动态规划简介、动态规划基础 与 计数 DP 页面。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考