統(tǒng)計(jì)[0,N]區(qū)間不包含4且不包含62的整數(shù)個(gè)數(shù)鲸郊。
狀態(tài)設(shè)計(jì)：
DP[pos][0] 表示當(dāng)前考慮pos位燕侠，不包含4和62畏腕，不以6結(jié)尾的統(tǒng)計(jì)數(shù)乘凸；
DP[pos][1] 表示不包含4和62，以6結(jié)尾的統(tǒng)計(jì)數(shù)党远；
狀態(tài)轉(zhuǎn)移時(shí)削解，只要跳過(guò)數(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));
}
}
