統(tǒng)計[0,N]區(qū)間不包含4且不包含62的整數(shù)個數(shù)。

狀態(tài)設(shè)計：
DP[pos][0] 表示當前考慮pos位，不包含4和62，不以6結(jié)尾的統(tǒng)計數(shù)；
DP[pos][1] 表示不包含4和62，以6結(jié)尾的統(tǒng)計數(shù)；

狀態(tài)轉(zhuǎn)移時，只要跳過數(shù)字4和2接上6的轉(zhuǎn)移即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[30][2];
int bit[30];
int dfs(int pos, int istop, int s){
    if (pos==-1) return 1;
    if (!istop && dp[pos][s]!=-1) return dp[pos][s];

    int lastbit = istop ? bit[pos] : 9;
    int ans = 0;
    for (int i=0;i<=lastbit;i++){
        if (i==4||(i==2&&s)) continue;
        ans += dfs(pos-1, istop&&i==lastbit, i==6);
    }

    if (!istop) dp[pos][s] = ans;
    return ans;
}

int calc(int n){
    if (n==0) return 1;
    int cnt = 0;
    while(n){
        bit[cnt++] = n%10;
        n /= 10;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(cnt-1,1,0);
}

int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)&&(n||m)){
        printf("%d\n", calc(m)-calc(n-1));
    }
}