求区间 L~R 之间的数中，满足某些条件的数的个数。
条件 1 般有 2 种，
对数字 “形” 的要求，比如数字要成山谷型，或不包含某段数字。
对数字 “数” 的要求，比如能被什么东西整除，每位之和怎么怎么样。
先把区间转成 1~R-1~L ，然后我们只用求出 1~N 满足条件的数的个数。
这时，我们 1 位 1 位推过去。
我们注意有两个让我们非常讨厌的东西，也是，数位 DP 特有的问题。
1，数字是有上界的，我们求的是 1~N 。 （如果不转成相减的形式，那就要考虑下界了）
2，数字是有前导零的，对于数字的 “形” 的要求，是通常要考虑前导零的。
1 般的，状态表示为，f[i,推到第 i 位][0/1,是否有上界][0/1,当前位是不是前导零][x,本位数字是什么]
(也可以用x=10表示前导零，而去掉那 1 维)
求 L~R 之间，满足每 1 位的数位，与它相邻 1 位，相邻 2 位，都不相同的数的个数。
比如：12324 不符合，12312 符合
前导零在这题，用数位=10
我们把状态设计如下：
f[i][0/1][x1][x2]，推到第 i 位，有无上界，x1,x2表示这 1 位和前 1 位是x1,x2，x1,x2=10 表示前导零。前导零可以相邻相同。
从低位往高位做，f[i][0][x1][x2]=sum(f[i-1][0][x2][x3]) (x1!=x2!=x3,0≤x1,x2,x3<10,前导零特判)
f[i][1][x1][x2]=sum(f[i-1][0][x2][x3]) (x1<lim,其他如上)
f[i][1][x1][x2]=sum(f[i-1][1][x2][x3]) (x1=lim,其他如上)
这里做 1 个小总结，对于上界的理解，
若没有上界，就可以任选，
若有，那么当选的数小于 limit，后面的数可以任选，若等于，后面的数也是有限制的。
这是 1 题对数的 “形” 要求，再来看 1 下这题，对 “数” 的要求的
给出 a,b，求出 [a,b] 中各位数字之和能整除原数的数的个数。1 ≤ a ≤ b ≤ 10^18
这题看起来难，但难不到我们会数位DP的同学。
首先我们不用管前导零~Yeah~
因为数位和都不大，最大是 9*位数=162 ，所以比较小，就可以为所欲为。
我们先枚举数位和 S 是多少，然后再来 DP
f[i][0/1][sum][mod],sum是数位和，mod 是数字 %S 的余数
当我们找到状态的表达，就可以用数位DP的套路DP了。
做多了就会了。要学会表示状态，和对上界与前导零的处理。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：Digit_DP”