关于数位 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