数位dp解不要62注释

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[10][3];
void Init(){    //预处理，算出所有可能
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=8;i++){
        dp[i][0]=dp[i-1][0]*9-dp[i-1][1];   //在不含不吉利数62和4的首位分别补除了4的9个数字，减去在2前面补6的个数
        dp[i][1]=dp[i-1][0];        //在不含不吉利数在首位补2
        dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];   //各种出现不吉利数的情况
        //在这里为什么不理解呢是因为他这个dp不是累积的和而是每次都单独算出这个位数的全排列
        //首位加零代表的是比它少一位数的全排列.
    }
}
int Solve(int x){
    int digit[15];
    int cnt=0,tmp=x;
    while(tmp){
        digit[++cnt]=tmp%10;
        tmp/=10;
    }
    digit[cnt+1]=0;
    int flag=0,ans=0;
    for(int i=cnt;i>0;i--){
        ans+=digit[i]*dp[i-1][2];   //由上位所有非吉利数推导
        //这里的第一次循环可以看作是从1至digit[i],
        if(flag)     //之前出现非吉利的数字
            ans+=digit[i]*dp[i-1][0];
        else{
            if(digit[i]>4)   //出现4
                ans+=dp[i-1][0];
            if(digit[i]>6)   //出现6
                ans+=dp[i-1][1];
            if(digit[i+1]==6 && digit[i]>2)  //出现62
                ans+=dp[i][1];//这个之所以不是i-1是由于,这个需要自己本省带2
            //而不是后面的带2的吉利数字简单地说前面两个时确定了自身后面变,这个是
            //确定了前一个,自己变
        }
        if(digit[i]==4 || (digit[i+1]==6 && digit[i]==2))
            flag=1;
    }
    return x-ans;   //所有的数减去非吉利的数
}
int main(){
    int a,b;
    Init();
    while(~scanf("%d%d",&a,&b)){
        if(a==0 && b==0)
            break;
        printf("%d\n",Solve(b+1)-Solve(a));
        //相当于求0~b的吉利数字减去,0~a-1的吉利数字
        //因为上文解法最后求得吉利数字是不包括传入参数本身的
        //之所以理解为×0~digit[i]-1,是因为digit[i]后面全是零的那个数
        //由小一位数的全排列里的零代替,每一次相加都会有后一位数的零
    }
    return 0;
}