[ZOJ3494]BCD Code

　　AC自动机+数位DP。

　　大致题意：

　　　　BCD码就是把一个数十进制下的每一位分别用4位的二进制表示。

　　　　给你一坨01串，问你在一个区间内，有多少个数的BCD码不包含任何一个字符串。

　　因为涉及到多个串的匹配问题...所以要在AC自动机上DP

　　f[i][j]表示在自动机上的节点i，再往后走j步 的合法方案数。（合法就是说，经过的路径上不包含任何一个给定字符串）

　　建完AC自动机后，把非法的节点都删掉，再求出CH[i][j]表示从i节点出发，经过数字j后到达的节点(0<=j<=9)，这样好转移= =。

　　一开始想写递归版本的。。前导0什么的完全无力TAT

　　后来干脆用记忆化搜索求f数组，然后统计答案的时候用正常姿势。。这样好写多了>_<

　　结果交完直接#1了。。我是没看出来自己的写法哪里常数优越= =

　　其实这题只比普通模版题多了个AC自动机而已。。。其他甚至还简单点

　　就算是递归版的，只要好好想一下前导零的问题就行了吧...网上递归版的标程也不长

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int modd=;

 int fail[],ch[][];

 int CH[][];

 int f[][],u[][];//f[i][j]在自动机上的i节点时，再往后走j步的合法方案数

 int i,j,k,n,m,tot,T,ans,len;

 bool gg[];

 char s[];int dl[];

 inline void insert(int len){

     int i,now=;

     for(i=;i<len;i++)

         s[i]-='',now=ch[now][s[i]]?ch[now][s[i]]:(ch[now][s[i]]=++tot);

     gg[now]=;

 }

 inline void build(){

     int l=,r=,i,now,tmp;

     while(l<r){

         now=dl[++l];

         for(i=;i<=;i++)if(ch[now][i]){

             for(tmp=fail[now];tmp&&!ch[tmp][i];tmp=fail[tmp]);

             fail[ch[now][i]]=(now==)?:ch[tmp][i];

             gg[ch[now][i]]|=gg[fail[ch[now][i]]]|gg[now];

             dl[++r]=ch[now][i];

         }else{

             for(tmp=fail[now];tmp&&!ch[tmp][i];tmp=fail[tmp]);

             ch[now][i]=ch[tmp][i];

         }

     }

     for(i=;i<=tot;i++)for(j=;j<=;j++)if(gg[ch[i][j]]||gg[i])ch[i][j]=-;

     for(i=;i<=tot;i++)if(!gg[i])

         for(j=;j<=;j++){

             for(now=i,k=;k&&now!=-;k>>=)

                 now=ch[now][(k&j)!=];

             CH[i][j]=now;//printf("   %d->%d %d\n",i,j,CH[i][j]);

         }

     for(i=;i<=tot;i++)if(!gg[i])f[i][]=,u[i][]=T;

 }

 inline int dfs(int x,int step){

     if(u[x][step]==T)return f[x][step];

     int ans=;

     for(int i=;i<=;i++)if(CH[x][i]!=-)

         ans+=dfs(CH[x][i],step-),ans-=ans>=modd?modd:;

     u[x][step]=T,f[x][step]=ans;//printf("   f: %d %d  %d\n",x,step,f[x][step]);

     return ans;

 }

 inline int get(int len){//求区间[1,len)内合法方案数

     register int i,j,ans=,now;

     for(i=;i<len;i++)s[i]-=;

     for(i=;i<len;i++)for(j=;j<=;j++)if(CH[][j]!=-)

         ans+=dfs(CH[][j],i-),ans-=ans>=modd?modd:;

     for(i=;i<s[];i++)if(CH[][i]!=-)ans+=dfs(CH[][i],len-),ans-=ans>=modd?modd:;

     now=CH[][s[]];

     for(i=;i<len&&now!=-;i++){

         for(j=;j<s[i];j++)if(CH[now][j]!=-)ans+=dfs(CH[now][j],len-i-),ans-=ans>=modd?modd:;

         now=CH[now][s[i]];

     }

     return ans;

 }

 inline void add(){

     int i,j;

     for(i=len-;i>=;i--)if(s[i]!='')break;

     if(i>=)

         for(s[i]++,j=i+;j<len;j++)s[j]='';

     else{

         for(s[]='',i=;i<=len;i++)s[i]='';

         len++;

     }

 }

 int main(){

     for(scanf("%d",&T);T;T--){

         scanf("%d",&n);memset(gg,,tot+);memset(ch,,(tot+)<<);tot=;

         for(i=;i<=n;i++)

             scanf("%s",s),insert(strlen(s));

         build();

         scanf("%s",s);len=strlen(s);ans=-get(len);

         scanf("%s",s);len=strlen(s);add();ans+=get(len);

         if(ans<)ans+=modd;

         printf("%d\n",ans);

     }

     return ;

 }