Description:

求 $[L,R]$ 内不含 $4$ 和 $62$ 的数。

$0<L\le R < 1000000$ 多组询问

Solution:

数位 $DP$ ，先处理出 $f[i][j]$ 表示第 $i$ 位数字为 $j$ 的方案数，对于不合法的状态转移时避免即可，即 $[j\times10^{i},(j+1)\times 10^{i})$ ，计算时用前缀和，因为区间右开，所以先将数字 $+1$ ，从高位向低位沿着边界处理，因为中间如果有不合法状态要 $break$ ，从低位开始处理时 $break$ 会少一些情况，如果边界出现了不合法的情况，直接 $break$ 掉，因为之后沿着边界走也不可避免他们。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

int f[10][10];

int bit[10],l;

void pre()

{

	memset(f,0,sizeof(f));

	f[0][0] = 1;

	for(int i = 1;i <= 7;++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];

			}

		}

	}

	return;

}

int calc(int t)

{

	++t;

	int ans = 0;

	l = 0;

	memset(bit,0,sizeof(bit));

	while(t > 0)

	{

		++l;

		bit[l] = t % 10;

		t /= 10;

	}

	for(int i = l;i >= 1;--i)

	{

		for(int j = 0;j < bit[i];++j)

		{

			if(bit[i + 1] == 6 && j == 2)continue;

			ans += f[i][j];

		}

		if(bit[i] == 4 || (bit[i + 1] == 6 && bit[i] == 2))break;

	}

	return ans;

}

int main()

{

	pre();

	while(scanf("%d%d",&n,&m) && n != 0 && m != 0)

	{

		cout << calc(m) - calc(n - 1) << endl;

	}

	return 0;

}