记录位置、这一位的数、上一位的数,然后比较三个数是否相同,相同则符合,还要两个参数记录是否出现4和8,要注意处理前导0
//记录最后出现的数字是几 上一位是几 是否已经有三连号 有没有出现8 有没有出现4 #include <bits/stdc++.h> using namespace std; #define int long long int f[13][11][13][2][2][2]; int a[13]; int dp(int pos,int num,int last,bool ok,bool have8,bool have4,bool flag,bool first) { if(pos==0) return ok&&((!have8)||(!have4)); if(flag&&f[pos][num][last][have8][have4]!=-1) return f[pos][num][last][have8][have4]; int x=flag?9:a[pos]; int ans=0; for(int i=0;i<=x;i++) { if(first&&i==0) continue; ans+=dp(pos-1,i,num,ok||(i==num&&i==last),have8||i==8,have4||i==4,flag||i<x,0); } if(flag) f[pos][num][last][have8][have4]=ans; return ans; } int cul(int x) { if(x<1e10) return 0; int pos=0; while(x) { a[++pos]=x%10; x/=10; } return dp(pos,0,0,0,0,0,0,1); } signed main() { memset(f,-1,sizeof(f)); int l,r; scanf("%lld%lld",&l,&r); printf("%lld\n",cul(r)-cul(l-1)); }