1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 int dp[10][2]; 5 int digit[10]; 6 //len 长度 state 是否上位为6 limit 是否达到上限 7 //dfs的值为，在digit数组限制下长度为len的数字的ans 8 int dfs(int len , int state , bool limit) 9 {10     // 如果找到个位数，则返回111     if (len == 0) return 1;12     //如果dfs到当前位置，数位没有限制，并且记忆化处理过len长度的数，则返回dp内容13     if (!limit && dp[len][state]!=-1)14         return dp[len][state];15     int tans = 0;16     //判断当前曾枚举范围，是0-9还是0-digit[len]17     int limitD = limit ? digit[len] : 9;18     //枚举当前位数字19     for (int i = 0 ; i <= limitD ; i++)20     {21         //如果枚举到4,或者state==1（即上一位为6的情况下）且枚举到2,那么不满足要求，跳过22         if ( i==4 || (state == 1 && i == 2) ) continue;23         //dfs,len位为i，数字长len-1 ans,24         //len-125         //当前位为6,即len的上一位为 626         //上一位有限制，并且当前位有限制，那么不能直接返回长27         tans += dfs(len-1 , i==6?1:0 , limit && i == digit[len]);28     }29     //如果是无限制的len长度的数字ans，那么存下来30     if (!limit) dp[len][state] = tans;31     return tans;32 }33 int solve(int x)34 {35     int cnt = 0;36     while (x!=0)37     {38        digit[++cnt] = x % 10;39        x/=10;40     }41     return dfs(cnt,0,true);42 }43 int main()44 {45     memset(dp,-1,sizeof dp);46     int a,b;47     while (cin >> a >> b && a+b!=0)48     {49         cout << solve(b) - solve(a-1) <<endl;50     }51 }