状态只要记录有没有出现过$4,8$,三连有没有出现就行,其他随便搞。

不过记忆化搜索总有东西解释不通。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,M=8555;
ll inf=1ll<<62;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll f[12][10][2][2][4][2];int a[13];//f1前后相等 f2是否三个相邻 f3存在4,8,f4是否达到上界 
inline int is48(int x){return (x==8)<<1|(x==4);} 
ll dfs(int pos,int x,int f1,int f2,int f3,int f4)
{
    if(f3==3)return 0;
    if(pos==1)return f2;
    if(f[pos][x][f1][f2][f3][f4]!=-1)return f[pos][x][f1][f2][f3][f4];
    ll &val=f[pos][x][f1][f2][f3][f4];val=0;int t=f4?a[pos-1]:9;
    for(int i=0;i<=t;i++)
    {
        int _f1=(i==x),_f2=f2||((i==x)&&f1),_f3=is48(i)|f3,_f4=f4&&(i==t);
        val+=dfs(pos-1,i,_f1,_f2,_f3,_f4);
    }
    return val;
}
ll solve(ll n)
{
    if(n<(int)1e10)return 0;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=11;i++,n/=10)a[i]=n%10;
    ll ans=0;
    for(int i=1;i<=a[11];i++)
        ans+=dfs(11,i,0,0,is48(i),i==a[11]);
    return ans;
}
int main()
{
    ll L,R;qr(L),qr(R);
    qw(solve(R)-solve(L-1));puts("");
    return 0;
}

宽搜

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,M=8555;
ll inf=1ll<<62;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node
{
    int k,x,f1,f2,f3,f4;
    node(int k=0,int x=0,int f1=0,int f2=0,int f3=0,int f4=0):k(k),x(x),f1(f1),f2(f2),f3(f3),f4(f4){}
}q[200005];
ll f[12][10][2][2][4][2];
int is48(int x){return ((x==8)<<1)|(x==4);}
ll solve(ll n)
{
    int l=1,r=0;
    memset(f,0,sizeof(f));int a[13];
    for(int i=11;i;i--,n/=10)a[i]=n%10;
    for(int i=1;i<=a[1];i++)
    {
        int f3=is48(i),f4=(i==a[1]);
        f[1][i][0][0][f3][f4]=1;
        q[++r]=node(1,i,0,0,f3,f4);
    }
    while(l<=r)
    {
        node s=q[l++];
        int k=s.k,x=s.x,f1=s.f1,f2=s.f2,f3=s.f3,f4=s.f4;ll val=f[k][x][f1][f2][f3][f4];
        if(k==11)continue;
        int t=f4?a[k+1]:9;
        for(int i=0;i<=t;i++)
        {
            int _f1=(x==i),_f2=f2||(f1&&_f1),_f3=f3|is48(i),_f4=f4&&(i==t);
            ll &w=f[k+1][i][_f1][_f2][_f3][_f4];
            if(!w)q[++r]=node(k+1,i,_f1,_f2,_f3,_f4);
            w+=val;
        }
    }
    ll w=0;
    for(int i=0;i<=9;i++)
        for(int f1=0;f1<=1;f1++)
        {
            int f2=1;
            for(int f3=0;f3<=2;f3++)
                w+=f[11][i][f1][f2][f3][0]+f[11][i][f1][f2][f3][1];
        }
    return w;
}
int main()
{
    ll L,R;qr(L),qr(R);
    qw(solve(R)-solve(L-1));puts("");
    return 0;
}