很惭愧,学到现在连数位dp都不会。做此题学习。

f[i][j]表示长为i的最高位是j的方案数.solve数组-1的原因是把0算进去了。

//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////

int n,m,f[10][10];
int solve(int n)
{
if (n==0) return 0;
int res=0,x=1000000,now=7,before=0,bbefore=0;
while (n<x) x/=10,now–;
rep(i,0,n/x-1) if (i!=4) res+=f[now][i];
if (now==1) res+=f[now][n/x];
before=n/x;n%=x;x/=10;now–;
while (x)
{
if (before!=4&&(!(before==2&&bbefore==6)))
{
rep(j,0,n/x-1) if (!(before==6&&j==2)) res+=f[now][j];
if (now==1&&(!(before==6&&n/x==2))) res+=f[now][n/x];
bbefore=before;before=n/x;
}
else return res-1;
n%=x;x/=10;now–;
}
return res-1;
}
int main()
{
rep(i,0,9) if (i!=4) f[1][i]=1;
rep(i,2,8)
rep(j,0,9)
if (j!=4) rep(k,0,9) if (k!=4&&(!(j==2&&k==6))) f[i][k]+=f[i-1][j];
while (scanf("%d%d",&n,&m)!=EOF)
{
if ((!n)&&(!m)) return 0;
printf("%d\n",solve(m)-solve(n-1));
}
return -1;
}