这题也就是一道数位DP裸题.
(尽管我写得很挫).
别看我代码.
(尽管注释很详细).
终于破除了我数位DP永远写不对的魔咒.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define pii pair<ll,ll>
#define uint unsigned ll
#define FILE "dealing"
ll read(){
ll x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
template<class T> bool cmax(T& a,T b){return a<b?a=b,true:false;}
template<class T> bool cmin(T& a,T b){return a>b?a=b,true:false;}
const int maxn=1010000;
ll f[13][11][2][2][2][2];
ll g[13][11][2][2][2][2][2];
ll n,m;
int w[20],r[20];
// pos la ch lianx 8 4 33 是否卡上界
int check(ll n){
int f1=0,f2=0;
r[0]=0;
while(n){r[++r[0]]=n%10;n/=10;}
up(i,1,11){
if(r[i]==4)f1=1;
if(r[i]==8)f2=1;
}
if(f1&&f2)return 0;
up(i,1,9){
if(r[i]==r[i+1]&&r[i+1]==r[i+2])return 1;
}
return 0;
}// 位置 最后字符 是否连续 8 4 是否有过三联 是否卡上界
ll dfs(int pos,int last,int f1,int f2,int f3,int f4,int f5){
if(pos==0){
if(f4)return 1;
return 0;
}
if(!f5){
ll ans=0;
for(int j=0;j<=9;j++){//最前数字
for(int k=0;k<=1;k++){//是否连续
for(int w=0;w<=1;w++){//8
for(int t=0;t<=1;t++){//4
for(int p=0;p<=1;p++){//是否三联过
if(w&&f3)continue;
if(t&&f2)continue;
if(!p&&!f4&&!(last==j&&(k||f1)))continue;
ans+=f[pos][j][k][w][t][p];
}
}
}
}
}
return ans;
}
else {//卡上界
ll ans=0;
int flag1,flag2,flag3,flag4;
for(int j=0;j<=w[pos];j++){//当前数字
if(j==4&&f2)continue;
if(j==8&&f3)continue;
flag1=flag2=flag3=flag4=0;
if(j==8||f2)flag1=1;if(j==4||f3)flag2=1;
if((j==last&&f1)||f4)flag3=1;
if(j==last)flag4=1;
ans+=dfs(pos-1,j,flag4,flag1,flag2,flag3,j==w[pos]);
}
return ans;
}
}
ll solve(ll n){
memset(w,0,sizeof(w));ll p=n;
while(n){
w[++w[0]]=n%10;
n/=10;
}
ll ans=0;
up(i,1,w[11]){
if(i!=4&&i!=8)ans+=dfs(10,i,0,0,0,0,i==w[11]);
if(i==4)ans+=dfs(10,i,0,0,1,0,i==w[11]);
if(i==8)ans+=dfs(10,i,0,1,0,0,i==w[11]);
}
return ans;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
up(i,0,9){
if(i!=8&&i!=4)f[1][i][0][0][0][0]=1;
if(i==8)f[1][i][0][1][0][0]=1;
if(i==4)f[1][i][0][0][1][0]=1;
}
int f1,f2,f3,f4;
for(int i=1;i<=11;i++){//位数
for(int j=0;j<=9;j++){//枚举当前最前方的数字
for(int k=0;k<=1;k++){//枚举这个数字是否连续两次以上
for(int w=0;w<=1;w++){//枚举8是否出现过
for(int t=0;t<=1;t++){//枚举4是否出现过
for(int p=0;p<=1;p++){//枚举以前是否出现过三个以上的情况
if(f[i][j][k][w][t][p]==0)continue;
for(int y=0;y<=9;y++){//枚举转移的方向
if(y==4&&w)continue;
if(y==8&&t)continue;
f1=f2=f3=f4=0;
if(y==8||w)f1=1;if(y==4||t)f2=1;
if((j==y&&k)||p)f3=1;
if(j==y)f4=1;
f[i+1][y][f4][f1][f2][f3]+=f[i][j][k][w][t][p];
}
}
}
}
}
}
}
n=read(),m=read();
printf("%lld
",solve(m)-solve(n-1));
return 0;
}