#include<cstdio> //code by Alphnia#include<cstring>#include<iostream>usingnamespacestd;#define N 50005#define ll long longlla,b;llf[15],ksm[15],p[15],now[15];lldfs(intu,intx,boolf0,boollim){// u 表示位数,f0 是否有前导零,lim 是否都贴在上限上if(!u){if(f0)f0=0;return0;}if(!lim&&!f0&&(~f[u]))returnf[u];llcnt=0;intlst=lim?p[u]:9;for(inti=0;i<=lst;i++){// 枚举这位要填的数字if(f0&&i==0)cnt+=dfs(u-1,x,1,lim&&i==lst);// 处理前导零elseif(i==x&&lim&&i==lst)cnt+=now[u-1]+1+dfs(u-1,x,0,lim&&i==lst);// 此时枚举的前几位都贴在给定的上限上。elseif(i==x)cnt+=ksm[u-1]+dfs(u-1,x,0,lim&&i==lst);elsecnt+=dfs(u-1,x,0,lim&&i==lst);}if((!lim)&&(!f0))f[u]=cnt;// 只有不贴着上限和没有前导零才能记忆returncnt;}llgans(lld,intdig){intlen=0;memset(f,-1,sizeof(f));while(d){p[++len]=d%10;d/=10;now[len]=now[len-1]+p[len]*ksm[len-1];}returndfs(len,dig,1,1);}intmain(){scanf("%lld%lld",&a,&b);ksm[0]=1;for(inti=1;i<=12;i++)ksm[i]=ksm[i-1]*10ll;for(inti=0;i<9;i++)printf("%lld ",gans(b,i)-gans(a-1,i));printf("%lld\n",gans(b,9)-gans(a-1,9));return0;}
#include<cstdio> //code by Alphnia#include<cstring>#include<iostream>usingnamespacestd;intx,y,dp[15][3],p[50];inlineintpre(){memset(dp,0,sizeof(dp));dp[0][0]=1;for(inti=1;i<=10;i++){dp[i][0]=dp[i-1][0]*9-dp[i-1][1];dp[i][1]=dp[i-1][0];dp[i][2]=dp[i-1][2]*10+dp[i-1][1]+dp[i-1][0];}}inlineintcal(intx){intcnt=0,ans=0,tmp=x;while(x){p[++cnt]=x%10;x/=10;}boolflag=0;p[cnt+1]=0;for(inti=cnt;i;i--){// 从高到低枚举数位ans+=p[i]*dp[i-1][2];if(flag)ans+=p[i]*dp[i-1][0];else{if(p[i]>4)ans+=dp[i-1][0];if(p[i]>6)ans+=dp[i-1][1];if(p[i]>2&&p[i+1]==6)ans+=dp[i][1];if(p[i]==4||(p[i]==2&&p[i+1]==6))flag=1;}}returntmp-ans;}intmain(){pre();while(~scanf("%d%d",&x,&y)){if(!x&&!y)break;x=min(x,y),y=max(x,y);printf("%d\n",cal(y+1)-cal(x));}return0;}
阅读题面发现,如果将数字看成字符串,那么这就是需要完成一个多模匹配,自然而然就想到 AC 自动机。普通数位 DP 中,先从高到低枚举数位,再枚举每一位都填什么,在这道题中,我们也就自然地转化为枚举已经填好的位数,再枚举此时停在 AC 自动机上的哪个节点,然后从当前节点转移到它在 AC 自动机上的子节点。
#include<bits/stdc++.h> //code by Alphniausingnamespacestd;#define N 1505#define ll long long#define mod 1000000007intn,m;chars[N],c[N];intch[N][10],fail[N],ed[N],tot,len;inlinevoidinsert(){intnow=0;intL=strlen(s);for(inti=0;i<L;++i){if(!ch[now][s[i]-'0'])ch[now][s[i]-'0']=++tot;now=ch[now][s[i]-'0'];}ed[now]=1;}queue<int>q;inlinevoidbuild(){for(inti=0;i<10;++i)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){intu=q.front();q.pop();for(inti=0;i<10;++i){if(ch[u][i]){fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]),ed[ch[u][i]]|=ed[fail[ch[u][i]]];}elsech[u][i]=ch[fail[u]][i];}}ch[0][0]=0;}llf[N][N][2],ans;inlinevoidadd(ll&x,lly){x=(x+y)%mod;}intmain(){scanf("%s",c);n=strlen(c);scanf("%d",&m);for(inti=1;i<=m;++i)scanf("%s",s),insert();build();f[0][0][1]=1;for(inti=0;i<n;++i){for(intj=0;j<=tot;++j){if(ed[j])continue;for(intk=0;k<10;++k){if(ed[ch[j][k]])continue;add(f[i+1][ch[j][k]][0],f[i][j][0]);if(k<c[i]-'0')add(f[i+1][ch[j][k]][0],f[i][j][1]);if(k==c[i]-'0')add(f[i+1][ch[j][k]][1],f[i][j][1]);}}}for(intj=0;j<=tot;++j){if(ed[j])continue;add(ans,f[n][j][0]);add(ans,f[n][j][1]);}printf("%lld\n",ans-1);return0;}