[数位DP][CQOI2016]手机号码(附数位DP模板)

#include<iostream>
#include<stdio.h>
#include<cstring>
#define LL long long
using namespace std;

LL dp[11][11][11][2][2][2];

int a[11];int cnt;

inline LL calc(int pos,int llast,int last,bool if4,bool if8,bool if3,bool head,bool limit){
    if(pos==-1) return if3?1:0;//如果出现过连续三个相同的数，才符合条件。 
    if(!limit && !head && last!=-1 && llast!=-1 && dp[pos][llast][last][if4][if8][if3]!=-1)
        return dp[pos][llast][last][if4][if8][if3];
    int up=limit?a[pos]:9;//上限。 
    int down=head?1:0;//下限。 
    LL tmp=0;
    for(int i=down;i<=up;++i){
        if(if4 && i==8) continue;//有4不能有8. 
        if(if8 && i==4) continue;//有8不能有4. 
        tmp+=calc(pos-1,last,i,if4||(i==4),if8||(i==8),if3||(llast==last&&last==i),0,limit && i==a[pos]);
        //传递条件就好啦。 
    }
    if(!limit && !head && last!=-1 && llast!=-1) dp[pos][llast][last][if4][if8][if3]=tmp;
    return tmp;
}

inline LL devide(LL x){
    cnt=-1;
    memset(a,0,sizeof a);
    while(x){
        a[++cnt]=x%10;
        x/=10;
    }
    return cnt!=10?0:calc(cnt,-1,-1,0,0,0,1,1);//不足11位返回零就好啦。
    //不要说不存在这种情况。
    //因为我们传的是l-1。所以l=100 0000 0000 时，l-1=99 9999 9999 辣。 
    
}

int main(){
    LL l,r;
    cin>>l>>r;
    memset(dp,-1,sizeof dp);
    cout<<devide(r)-devide(l-1);
    return 0;
}

#include<iostream>
#include<stdio.h>
#include<cstring>
#define LL long long
using namespace std;

LL dp[11][11][11][2][2][2];

int a[11];int cnt;

inline LL calc(int pos,int llast,int last,bool if4,bool if8,bool if3,bool head,bool limit){
    if(pos==-1) return if3?1:0;//如果出现过连续三个相同的数，才符合条件。 
    if(!limit && !head && last!=-1 && llast!=-1 && dp[pos][llast][last][if4][if8][if3]!=-1)
        return dp[pos][llast][last][if4][if8][if3];
    int up=limit?a[pos]:9;//上限。 
    int down=head?1:0;//下限。 
    LL tmp=0;
    for(int i=down;i<=up;++i){
        if(if4 && i==8) continue;//有4不能有8. 
        if(if8 && i==4) continue;//有8不能有4. 
        tmp+=calc(pos-1,last,i,if4||(i==4),if8||(i==8),if3||(llast==last&&last==i),0,limit && i==a[pos]);
        //传递条件就好啦。 
    }
    if(!limit && !head && last!=-1 && llast!=-1) dp[pos][llast][last][if4][if8][if3]=tmp;
    return tmp;
}

inline LL devide(LL x){
    cnt=-1;
    memset(a,0,sizeof a);
    while(x){
        a[++cnt]=x%10;
        x/=10;
    }
    return cnt!=10?0:calc(cnt,-1,-1,0,0,0,1,1);//不足11位返回零就好啦。
    //不要说不存在这种情况。
    //因为我们传的是l-1。所以l=100 0000 0000 时，l-1=99 9999 9999 辣。 
    
}

int main(){
    LL l,r;
    cin>>l>>r;
    memset(dp,-1,sizeof dp);
    cout<<devide(r)-devide(l-1);
    return 0;
}