數位dp+AC自動機 [cpp] #include <cstdio> #include <cstring> #include <algorithm> #include <queue> typedef long long ll; using namespace std; ll l,r; char a[20],b[20]; int aa[20]; int next[100][10],pos,fail[100]; bool ok[100]; void insert(char * s){ int k,i,p=0; for(i=0;s[i];i++){ k=s[i]-'0'; p=next[p][k]?next[p][k]:next[p][k]=pos++; } ok[p]=1; } void makefail(){ int i; queue<int>q; q.push(0); while(!q.empty()){ int u=q.front(); q.pop(); for(i=0;i<10;i++){ int v=next[u][i]; if(v==0)next[u][i]=next[fail[u]][i]; else q.push(v); if(v!=0 && u!=0){ fail[v]=next[fail[u]][i]; ok[v]|=ok[fail[v]]; } } } } ll dp[20][100][2]; //第一維表示當前第幾位，第二維表示當前的state，第三維表示此前的所有位是否為0 ll dfs(int pos,int sta,int doing,int pre){ if(pos==-1) return ok[sta]; if(!doing && dp[pos][sta][pre]!=-1)return dp[pos][sta][pre]; int i=(pre==0)?0:1; int j=doing?aa[pos]:9; int newsta; ll ans=0; for(;i<=j;i++){ if(ok[sta])newsta=sta; else newsta=next[sta][i]; ans+=dfs(pos-1,newsta,doing && (i==j),!((pre==0)&&(i==0))); } if(!doing)dp[pos][sta][pre]=ans; return ans; } ll solve(ll u){ if(u==0)return 0; int i=0; while(u){ aa[i++]=u%10; u/=10; } i--; memset(dp,-1,sizeof(dp)); return dfs(i,0,1,0); } int main(){ int t,T,i; scanf("%d",&T); for(t=1;t<=T;t++){ memset(next,0,sizeof(next)); memset(fail,0,sizeof(fail)); memset(ok,0,sizeof(ok)); scanf("%lld %lld",&l,&r); scanf("%s %s",a,b); pos=1; insert(a); insert(b); makefail(); printf("%lld\n",solve(r)-solve(l-1)); } return 0; }
