关于数位 DP 的一点点

数位 DP 用于解决如下格式的问题：
给定一个闭区间 $[L,R]$，让你求这个区间中满足 某种条件 的数的总数。

数位 DP 是一个很朴素的想法，其实就是枚举每一位的情况，再加了一个公共部分的缓存。
对于多组测试数据的题目，两组测试数据之间不用清缓存（因为缓存针对的是普遍情况，而边界情况是暴力统计不缓存的，所以缓存可以共用）。

个人感觉，在数位 DP 的实现上 记忆化 DFS 比 DP 要好写一点。
数位 DP 的一个特点是 dfs(x, y, z) 在 (x, y, z) 这个三元组确定的情况下是可以确定的，所以可以缓存下来。但是在边界情况时缓存不具有普遍性，于是暴力统计。

数位 DP 干了一件这样的事情：暴力统计的枚举方式是 $\operatorname{for} i \in [l,r]$，没有公共部分，但是数位 DP 的统计方式是每一位确定过去，这使得它有一个优势，就是出现了大量的重复，可以进行优化。

【LightOJ 1140】How Many Zeroes?

题面 ᴮᵃᶜᵏᵘᵖ

题意

求区间 $[m,n]$ 中的数字的十进制表示中总共有多少个 $0$

代码 ᴮᵃᶜᵏᵘᵖ

【HDU 2089】不要 62

题面 ᴮᵃᶜᵏᵘᵖ

题意

求区间 $[m,n]$ 中，十进制表示中既不包含连续的 $62$，也不包含 $4$ 的数的个数。

代码 ᴮᵃᶜᵏᵘᵖ

【HDU 3555】Bomb

题面 ᴮᵃᶜᵏᵘᵖ

题意

求区间 $[1,N]$ 中数字的十进制表示包含连续 $49$ 的数字个数

代码 ᴮᵃᶜᵏᵘᵖ

可以参考注释理解

【SPOJ BALNUM】Balanced Numbers

题面 ᴮᵃᶜᵏᵘᵖ

题意

在下列情况下，正整数被视为平衡数：

1. 每个偶数数字在其十进制表示形式中出现奇数次
2. 每个奇数数字在其十进制表示形式中出现偶数次

上面的翻译比较垃圾，大概理解一下

例如，$77$、$211$、$6222$ 和 $112334445555677$ 是平衡数，而 $351$、$21$ 和 $662$ 不是平衡数。

给定区间 $[A,B]$，求其中平衡数的个数。

代码 ᴮᵃᶜᵏᵘᵖ

可以参考注释理解

【SPOJ MYQ10】Mirror Number

题面 ᴮᵃᶜᵏᵘᵖ

题意

镜面对称数是仅包含 $0$、$1$ 和 $8$ 的回文数

求 $[a,b]$ 中有几个镜面对称数

代码 ᴮᵃᶜᵏᵘᵖ

数据范围是 $10^{44}$，所以要开一个字符数组来存输入
并且特判一下 $a$ 本身是不是回文数

---

如果需要编译运行，可以前往 Gist ᴮᵃᶜᵏᵘᵖ 复制公共头

如果编译器不支持 C++11，请将 constexpr 改为 const