数位DP

参考《算法竞赛进阶指南》、AcWing题库

数位统计 DP 是与数字相关的一类计数问题。在这类题目中, 一般给定一些限制条件, 求满足限制条件的第 $K$ 小的数是多少, 或者求在区间 $[L, R]$ 内有多少个满足限制条件的数。解决方法与例题 “A Decorative Fence” 类似, 先用动态规划进行预处理, 再基于拼凑思想, 用 “试填法” 求出最终的答案。

数位DP基本概念

数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。

如果拆的是 十进制数，那么每一位数字都是 $0$ ~ $9$ ，其他进制可类比十进制。

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）
这些条件经过转化后可以使用「数位」的思想去理解和判断
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制
上界很大（比如 $10^9$ ），暴力枚举验证会超时

数位DP的基本原理：
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推/DP 的方式进行状态转移。

数位 DP 中通常会利用常规计数问题技巧，求 一段区间 内符合某些条件的数的个数，用 前缀和思想 转换为求两个 前缀区间 的问题，把一个区间内的答案拆成两部分相减

$ans[l,r] = ans[1,r] - ans[1,l-1]$

那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。

310. 启示录

题目描述

古代人认为 $666$ 是属于魔鬼的数。

不但如此，只要某数字的十进制表示中有三个连续的 $6$ ，古代人也认为这是个魔鬼的数，比如 $666,1666,6663,16666,6660666$ 等等。

古代典籍中经常用“第 $X$ 小的魔鬼的数”来指代这些数，这给研究人员带来了极大的不便。

现在请编写一个程序，可以实现输入 $X$ ，输出对应的魔鬼数。

输入格式

第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。

每组测试数据占一行，包含一个整数 $X$ 。

输出格式

每组测试数据占一行，输出一个魔鬼数。

数据范围

$1 \le T \le 1000$ ,
$1 \le X \le 5*10^7$

输入样例：

输出样例：

1
2
3

1666
2666
66666

算法分析

设 $F[i, 3]$ 表示由 $i$ 位数字构成的魔鬼数有多少个, $F[i, j](0 \leq j \leq 2)$ 表示由 $i$ 位数字构成的、开头已经有连续 $j$ 个 6 的非魔鬼数有多少个。注意, 在计算 $F$ 时, 我们允许前导 0 的存在。

考虑第 $i$ 位 (最高位) 是什么数字, 容易得到状态转移方程:

$\begin{gathered} F[i, 0]=9 *(F[i-1,0]+F[i-1,1]+F[i-1,2]) \\ F[i, 1]=F[i-1,0] \\ F[i, 2]=F[i-1,1] \\ F[i, 3]=F[i-1,2]+10 * F[i-1,3] \end{gathered}$

动态规划完成后, 我们先通过 $F[i, 3]$ 确定第 $X$ 小的魔鬼数的位数。然后按照 “试填法” 的思想, 从左到右依次考虑每个数位, 同时记录当前末尾已经有连续的几个 6 。

从小到大枚举当前数位填什么数字, 通过预处理的 $F$ 数组可以直接计算出后边的数位有多少种填法可以得到魔鬼数, 与 $X$ 比较即可。详细步骤请看参考程序:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[21][4];
int t, n, m;

void prework() {
	f[0][0] = 1;
	for (int i = 0; i < 20; i++) {
		for (int j = 0; j < 3; j++) {
			f[i + 1][j + 1] += f[i][j];
			f[i + 1][0] += f[i][j] * 9;
		}
		f[i + 1][3] += f[i][3] * 10;
	}
}

int main() {
	prework();
	cin >> t; // 数据组数
	while (t--) {
		scanf("%d", &n); // 题目中的X
		// 第n个魔鬼数有m位
		for (m = 3; f[m][3] < n; m++);
		// 试填第i位，末尾已有k个6（k=3也表示已经是魔鬼数）
		for (int i = m, k = 0; i; i--) {
			// 从小到大枚举第i位填的数字j
			for (int j = 0; j <= 9; j++) {
				// 求出后边的i-1位有多少种填法能让整个数是魔鬼数
				long long cnt = f[i - 1][3];
				if (j == 6 || k == 3)
					for (int l = max(3 - k - (j == 6), 0); l<3; l++)
						cnt += f[i - 1][l];
				// 如果cnt比n小，说明第n个魔鬼数的第i位应该比j更大
				if (cnt < n) {
					n -= cnt;
				}
				// 否则，第i位就应该是j
				else {
					if (k < 3) {
						if (j == 6) k++; else k = 0;
					}
					printf("%d", j);
					break;
				}
			}
		}
		cout << endl;
	}
}

图像_2021-09-06_205520.png

预处理 $f(i,j)$ 后，我们可以求出第 $X$ 小的魔鬼数的位数 $cnt$ ，然后就是从高位开始，确定每一位的值是多少了？

$\color{red}{如何确定每一位的值？}$

第一步，我们可以先算下有多少个魔鬼数，首先是 $i-1$ 位的魔鬼数，然后从 $0~9$ 遍历 $i$ 位数字时，可能这位数字是 $6$ ，当其为 $6$ 或前 $i$ 的前 $3$ 个数都为 $6$ 时，再加上可能的魔鬼数，这样遍历 $i$ 位时总的魔鬼数就算出来了，当魔鬼数 $cnt<X$ 时，说明当前遍历的这个数 $i$ 太小了，这时 $X$ 要： $X-cnt$ 。

$\color{red}{为什么?}$

假设我们要求第19小的魔鬼数（9666)，从 $0$ 开始遍历最高位，后面可能的魔鬼数为 $1$ ， $19-1$ 表示从 $0666$ 开始排名为 $18$ 的魔鬼数

所以 $X-cnt$ 的作用即：在 $i$ 位为 $j$ 时的最大魔鬼数的基础上即 $i$ 位为 $j+1$ 时第 $X-cnt$ 个魔鬼数即答案~

当 $cnt\geq X$ 时，由于 $cnt$ 指的是当前位为 $j$ 时的可能的所有魔鬼数，而我们要求的是 $i$ 位为 $j$ 中第 $X$ 大的魔鬼数，说明此时 $i$ 位为 $j$ 包含了答案， $j$ 正是第 $i$ 位，接着记录有多少个连续的6，下一位同样如此处理

时间复杂度: $O(10mT)$

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

long long f[21][4];

void prework() {
  f[0][0] = 1;
  for (int i = 1; i < 20; ++i) {
    f[i][0] = 9 * (f[i - 1][0] + f[i - 1][1] + f[i - 1][2]);
    f[i][1] = f[i - 1][0];
    f[i][2] = f[i - 1][1];
    f[i][3] = f[i - 1][2] + 10 * f[i - 1][3];
  }
}

int main() {
  prework();
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    
    int m = 3;
    while (f[m][3] < n) ++m;
    // 试填第 i 位，紧临第 i 位前已有 k 个 6 (k = 3 也表示已经是魔鬼数)
    for (int i = m, k = 0; i >= 1; --i) {
      // 从小到大枚举第 i 位填的数字 j 
      for (int j = 0; j <= 9; ++j) {
		// 求出后边的 i - 1 位有多少种填法能让整个数是魔鬼数
        long long cnt = 0;
        //① 先加上前i - 1位已经是魔鬼数的情况
        cnt += f[i - 1][3];

        //② 再计算前i - 1位不是魔鬼数，但加上第i位后整个数是魔鬼数的情况
        //k < 3 时表示在m ~ j + 1位，末尾有连续k个6
        //k = 3 时表示在m ~ j + 1位，已经出现过连续3个6了
        if (j == 6 || k == 3) {
          int need; // need 表示后边的 i - 1 位开头需要有 need 个 6

          if (k == 3) need = 0;
          else if (j == 6) need = 3 - (1 + k);

          while (need <= 2) cnt += f[i - 1][need++];
        }
        
        //如果cnt比n小，说明第n个魔鬼数的第i位比j大
        if (cnt < n) {
          n -= cnt;
        } else { //否则，第n个魔鬼数第i位就是j
          if (k < 3) {
            if (j == 6) ++k;
            else k = 0;
          }
          cout << j;
          break;
        }
      }
    }
    cout << endl;
  }
}

311. 月之谜

题目描述

如果一个十进制数能够被它的各位数字之和整除，则称这个数为“月之数”。

给定整数 $L$ 和 $R$ ，你需要计算闭区间 $[L,R]$ 中有多少个“月之数”。

输入格式

输入占一行，包含两个整数 $L$ 和 $R$ 。

输出格式

输出一个整数，表示月之数的个数。

数据范围

$1 \le L,R < 2^{31}$

输入样例：

1 100

输出样例：

算法分析

设 $F[i, j, k, l]$ 表示由 $i$ 位数字构成、各位数字之和是 $j$ 、对 $k$ 取模余数是 $l$ 的数有多少个。在计算 $F$ 时, 允许前导 0 的存在。枚举第 $i$ 位的数字 $p$ , 得到状态转移方程:

$F[i, j, k, l]=\sum_{p=0}^{9} F\left[i-1, j-p, k,\left(l-p * 10^{i-1}\right) \bmod k\right]$

闭区间 $[L, R]$ 中月之数的个数, 等于 $[1, R]$ 中月之数的个数减去 $[1, L-1]$ 中月之数的个数。接下来以 $[1, R]$ 为例进行说明。

我们还是采取 “试填法” 的思想, 从高位到低位给每一位填数, 只要填了一个比上限 $R$ 要小的数位, 那么后边的数位无论是多少, 整个数值都不会超过 $R$ 。此时就可以立即把动态规划预处理出的结果累加到答案中。只有在每一位上始终填写与上限 $R$ 相同的数字时, 才需要继续向后扫描, 所以最终的计算量是数值的 “位数” 级别的, 非常小。

具体来说, 我们枚举最终的各位数字之和 $sum$ , 然后从左到右扫描每个数位, 设当前正在处理第 $i$ 位 (最高位为第 $N$ 位, 最低位为第 1 位), 当前已经填写的数字之和是 $t$ , 当前数值对 sum 取模余数是 $q$ 。我们从小到大枚举第 $i$ 位要填的数字 $p$ 。

若 $p$ 小于上限 $R$ 在第 $i$ 位上的数字, 则后边 $i-1$ 位可以随便填。因为最终的数值能被 sum 整除, 所以第 $1 \sim i$ 位构成的数值对 sum 取模余数应该是 $sum-q$ 。因此答案直接累加 $F\left[i-1\right., sum -t-p, sum, \left(\right. sum \left.\left.-q-p * 10^{i-1}\right) \bmod sum\right]$ 。
否则, 令 $t=t+p, q=\left(q+p * 10^{i-1}\right) \bmod s u m$ , 开始处理第 $i-1$ 位。

动态规划的计算量约为 $10 * 9^{7}$ , 每个测试点查询的计算量约为 $3000 * 10 * 9$ 。

Solution

338. 计数问题

题目描述

给定两个整数 $a$ 和 $b$ ，求 $a$ 和 $b$ 之间的所有数字中 $0 \sim 9$ 的出现次数。

例如， $a=1024，b=1032$ ，则 $a$ 和 $b$ 之间共有 $9$ 个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 $10$ 次，1 出现 $10$ 次，2 出现 $7$ 次，3 出现 $3$ 次等等…

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含两个整数 $a$ 和 $b$ 。

当读入一行为 0 0 时，表示输入终止，且该行不作处理。

输出格式

每组数据输出一个结果，每个结果占一行。

每个结果包含十个用空格隔开的数字，第一个数字表示 0 出现的次数，第二个数字表示 1 出现的次数，以此类推。

数据范围

$0 < a,b < 100000000$

输入样例：

输出样例：

1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

算法分析

Solution

1081. 度的数量

题目描述

求给定区间 $[X,Y]$ 中满足下列条件的整数个数：这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和。

例如，设 $X = 15, Y = 20, K = 2, B = 2$ ，则有且仅有下列三个数满足题意：

$17 = 2^4 + 2^0$
$18 = 2^4 + 2^1$
$20 = 2^4 + 2^2$

输入格式

第一行包含两个整数 $X$ 和 $Y$ ，接下来两行包含整数 $K$ 和 $B$ 。

输出格式

只包含一个整数，表示满足条件的数的个数。

数据范围

$1 \le X \le Y \le 2^{31}-1$ ,
$1 \le K \le 20$ ,
$2 \le B \le 10$

输入样例：

1
2
3

15 20
2
2

输出样例：

算法分析

数位DP基本概念

数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。

如果拆的是 十进制数，那么每一位数字都是 $0$ ~ $9$ ，其他进制可类比十进制。

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）
这些条件经过转化后可以使用「数位」的思想去理解和判断
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制
上界很大（比如 $10^9$ ），暴力枚举验证会超时

$ans[l,r] = ans[1,r] - ans[1,l-1]$

记忆化搜索 中要引入的参数通常有：

当前枚举到的数位 $pos$ （搜索的深度）
前一位数（或是前几位数）的情况 $st$ （诸如 前一位是什么、前几位总和是多少、某个数出现了几次 等）
前几位的数字是否等于上界的前几位数字 $op~(0/1)$ （限制本次搜索的数位范围）
是否有前导零 $lead~(0/1)$

本题图解：

在这里插入图片描述

数位Dp - 度的数量.png

QQ浏览器截图20210122131839.png

参考：

Solution

循环迭代递推

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 32;

int K, B;
int f[N][N];

void prework() { // 求组合数C_{i}^{j}
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= i; ++j) {
      if (j == 0) f[i][j] = 1;
      else f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; 
    }
  }
}
//求区间[0,n]中的 “满足条件的数” 的个数
//“满足条件的数”是指：一个数的B进制表示，其中有K位是1、其他位全是0
int dp(int n) {
  if (n == 0) return 0;//特判边界
  
  vector<int> nums;//存放n在B进制下的每一位
  while (n) nums.push_back(n % B), n /= B;//把n在B进制下的每一位单独拿出来
  
  int res = 0;//答案：[0,n]中共有多少个合法的数
  //last在数位dp中存的是：右边分支往下走的时候保存前面的信息 
  //遍历当前位的时候，记录之前那些位已经占用多少个1，那么当前还能用的1的个数就是K-last
  int last = 0;
  for (int i = nums.size() - 1; i >= 0; --i) {//从高位到低位枚举
    int x = nums[i];
    //只有x>0的时候才可以讨论左右分支
    //当x=0时，该位只能填上特定值，只存在右分支
    //当前位 = 0 ~ x - 1属于左分支，当前位 = x，属于右分支
    if (x) { //左边分支
      res += f[i][K - last];//左分支中当前位取0，后面0 ~ i - 1共i个位置中取K-last个1
      if (x > 1) {
        //左分支中当前位取1，后面0 ~ i - 1共i个位置中取K-last-1个1
        int lack = K - last - 1;
        if (lack >=  0) res += f[i][lack];
        break;// 因为此题只能取0或1，故左分支取>1和右分支取>1的情况均无效
      } 
      //上面统计完了**左分支**的所有情况，和右分支大于1的情况
      
      if (x == 1) {
        //对应于：右分支为1的情况，即限定值为1的情况，也就是左分支只能取0
        //此时的处理是，直接放到下一位来处理
        //只不过下一位可使用的1的个数会少1，体现在代码上是last+1
        ++last;
        if (last > K) break; //如果已经填的个数last > 需要填的个数K，不合法break
      }
    }
    if (i == 0 && last == K) ++res;
  }
  
  return res;
}

int dpp(int n) {
    if (n == 0) return 0;
    vector<int> num;
    while (n) num.push_back(n % B), n /= B;
    
    int cnt = 0;
    int last = 0;
    
    for (int i = num.size() - 1; i >= 0; --i) {
        int x = num[i];
        if (x == 0) {
            if (last > K) break;
        } else {
            cnt += f[i][K - last];
            if (x > 1) {
                if (last < K) cnt += f[i][K -last - 1];
                break;
            } else if (x == 1) {
                ++last;
                if (last > K) break;
            }
        }
        if (i == 0 && last == K) ++cnt;
    }
    return cnt;
}

int main() {
  prework();
  int l, r;
  cin >> l >> r >> K >> B;
  
  cout << dp(r) - dp(l - 1);
}

1082. 数字游戏

题目描述

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 $123$ ， $446$ 。

现在大家决定玩一个游戏，指定一个整数闭区间 $[a,b]$ ，问这个区间内有多少个不降数。

输入格式

输入包含多组测试数据。

每组数据占一行，包含两个整数 $a$ 和 $b$ 。

输出格式

每行给出一组测试数据的答案，即 $[a,b]$ 之间有多少不降数。

数据范围

$1 \le a \le b \le 2^{31}-1$

输入样例：

1
2

1 9
1 19

输出样例：

1
2

9
18

算法分析

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 15;

int f[N][10];//f[i][j]一共有i位，且最高位是j的非降数的个数

void prework() {
  for (int i = 1; i <= 10; ++i) {
    for (int j = 0; j <= 9; ++j) {
      if (i == 1) {
        f[i][j] = 1;
        continue;
      }
      for (int k = j; k <= 9; ++k) {
        f[i][j] += f[i - 1][k];
      }
    }
  }
}

int dp(int n) {
  if (n == 0) return 1;
  
  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;
  
  int res = 0, last = 0;
  for (int i = nums.size() - 1; i >= 0; --i) {
    int x = nums[i];
    
    for (int j = last; j < x; ++j) res += f[i + 1][j];//计算左分支
    
    if (x < last) break;
    last = x;//存储右分支信息，右分支到最后才会计算
    
    if (i == 0) res++;
  }
  
  return res;
}

int main() {
  prework();
  int l, r;
  while (cin >> l >> r) cout << dp(r) - dp(l - 1) << endl;
}

1083. Windy数

题目描述

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 Windy 数。

Windy 想知道，在 $A$ 和 $B$ 之间，包括 $A$ 和 $B$ ，总共有多少个 Windy 数？

输入格式

共一行，包含两个整数 $A$ 和 $B$ 。

输出格式

输出一个整数，表示答案。

数据范围

$1 \le A \le B \le 2 \times 10^9$

输入样例1：

1 10

输出样例1：

输入样例2：

25 50

输出样例2：

算法分析

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 11;

int f[N][10];

void prework() {
  for (int i = 1; i <= 10; ++i) {
    for (int j = 0; j <= 9; ++j) {
      if (i == 1) {
        f[i][j] = 1;
        continue;
      }
      for (int k = 0; k <= 9; ++k) 
        if (abs(j - k) >= 2) f[i][j] += f[i - 1][k];
    } 
  }
}

int dp(int n) {
  if (n == 0) return 0;
  
  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;
  
  int res = 0;
  int last = -2;

  for (int i = nums.size(); i >= 1; --i) {
    int x = nums[i - 1];
      
    for (int j = (i == nums.size()); j < x; ++j) 
      if (abs(j - last) >= 2) res += f[i][j];
    
    if (abs(x - last) >= 2) last = x;
    else break;
    
    if (i == 1) ++res;
  }
  
  for (int i = 1; i < nums.size(); ++i) 
    for (int j = 1; j <= 9; ++j) res += f[i][j];
  
  return res;
}

int main() {
  prework();
  
  int l, r;
  cin >> l >> r;
  
  cout << dp(r) - dp(l - 1);
}

1084. 数字游戏 II

题目描述

由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和 $mod\ N$ 为 $0$ 。

现在大家又要玩游戏了，指定一个整数闭区间 $[a.b]$ ，问这个区间内有多少个取模数。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含三个整数 $a,b,N$ 。

输出格式

对于每个测试数据输出一行结果，表示区间内各位数字和 $mod\ N$ 为 $0$ 的数的个数。

数据范围

$1 \le a,b \le 2^{31}-1$ ,
$1 \le N < 100$

输入样例：

1 19 9

输出样例：

算法分析

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 11, M = 110;

int f[N][10][M];
int p;

int mod(int x, int y) {
  return (x % y + y) % y;
}

void prework() {
  memset(f, 0, sizeof f);
  for (int j = 0; j <= 9; ++j) f[1][j][j % p]++;
  
  for (int i = 2; i < N; ++i) {
    for (int j = 0; j <= 9; ++j) {
      for (int k = 0; k < p; ++k) {
        for (int x = 0; x <= 9; ++x) {
          f[i][j][k] += f[i - 1][x][mod(k - j, p)];
        }
      }
    }
  }
}

int dp(int n) {
  if (n == 0) return 1;
  
  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;
  
  int res = 0;
  int last = 0;
  for (int i = nums.size(); i >= 1; --i) {
    int x = nums[i - 1];
    
    for (int j = 0; j < x; ++j) 
      res += f[i][j][mod(-last, p)];
    
    last += x;
    
    if (i == 1 && last % p == 0) res++;
  }
  
  return res;
}

int main() {
  int l, r;
  while (cin >> l >> r >> p) {
    prework();
    
    cout << dp(r) - dp(l - 1) << endl;
  }
}

1085. 不要62

题目描述

杭州人称那些傻乎乎粘嗒嗒的人为 $62$ （音：laoer）。

杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有 $4$ 或 $62$ 的号码。例如： $62315,73418,88914$ 都属于不吉利号码。但是， $61152$ 虽然含有 $6$ 和 $2$ ，但不是连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照号区间 $[n,m]$ ，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含一个整数对 $n$ 和 $m$ 。

当输入一行为“0 0”时，表示输入结束。

输出格式

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

数据范围

$1 \le n \le m \le 10^9$

输入样例：

1
2

1 100
0 0

输出样例：

算法分析

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 15;
int f[N][10];

void prework() {
  for (int i = 0; i <= 9; ++i) 
    if (i != 4) f[1][i] = 1;
  
  for (int i = 2; i < N; ++i) {
    for (int j = 0; j <= 9; ++j) {
      if (j == 4) continue;
      for (int k = 0; k <= 9; ++k) {
        if (k == 4 || j == 6 && k == 2) continue;
        f[i][j] += f[i - 1][k];
      }
    }
  }
}

int dp(int n) {
  if (n == 0) return 1;
  
  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;
  
  int res = 0;
  int last = 0;
  for (int i = nums.size(); i >= 1; --i) {
    int x = nums[i - 1];
    
    for (int j = 0; j < x; ++j) {
      if (j == 4 || last == 6 && j == 2) continue;
      res += f[i][j];
    }
    
    if (x == 4 || last == 6 && x == 2) break;
    last = x;
    
    if (i == 1) res ++;
  }
  
  return res;
}

int main() {
  prework();
  int l, r;
  while (cin >> l >> r, l || r) {
    cout << dp(r) - dp(l - 1) << endl;
  }
}