考研路茫茫——单词情结
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3580 Accepted Submission(s): 1037
Problem Description
背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele也终于要开始背单词了。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。
于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。
比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为
(2个) aa,ab,
(26个)aaa,aab,aac...aaz,
(26个)aba,abb,abc...abz,
(25个)baa,caa,daa...zaa,
(25个)bab,cab,dab...zab。
这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。
于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。
比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为
(2个) aa,ab,
(26个)aaa,aab,aac...aaz,
(26个)aba,abb,abc...abz,
(25个)baa,caa,daa...zaa,
(25个)bab,cab,dab...zab。
这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。
Input
本题目包含多组数据，请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。
Output
对于每组数据，请在一行里输出一共可能的单词数目。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。
Sample Input
2 3
aa ab
1 2
a
Sample Output
104
52
ans是包含模式串的串个数，用总个数减去不包含的即可
总个数:f[i]（小于等于i的所有字串）=f[i-1]*26+1，这个可以用矩阵乘法来实现
不包含的：如果单纯求走i步不包含，直接矩阵乘即可，现在要求1到i步的总和，在矩阵外加一维L+1，把a[i][L+1]都赋为1，即可实现求和
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<iostream> using namespace std; typedef unsigned long long ll; struct node{ node *fail; node *son[26]; bool pp; int num; node() { fail=NULL; for(int i=0;i<26;i++)son[i]=NULL; pp=true; num=0; } } *que[101]; node *ac[101]; node *root; ll a[101][101],b[101][101],c[101][101]; ll xzq,mus; char s[1011]; int len,tot,i,n,m; void Read() { char c; while(c=getchar(),c<'a'||c>'z'); s[++len]=c; while(c=getchar(),c>='a'&&c<='z')s[++len]=c; } void add() { node *p; p=root; int i,t; for(i=1;i<=len;i++){ t=s[i]-'a'; if(p->son[t]==NULL){ p->son[t]=new node(); p->son[t]->num=++tot; ac[tot]=p->son[t]; } p=p->son[t]; } p->pp=false; } void bfs() { int l,r,i; node *p; node *q; que[l=r=1]=root; while(l<=r){ p=que[l]; for(i=0;i<=25;i++)if(p->son[i]!=NULL){ r++; que[r]=p->son[i]; if(p==root)p->son[i]->fail=root; else{ q=p->fail; while(q!=NULL){ if(q->son[i]!=NULL){ p->son[i]->fail=q->son[i]; break; } q=q->fail; } if(p->son[i]->fail==NULL)p->son[i]->fail=root; } } l++; } for(i=2;i<=r;i++)que[i]->pp&=que[i]->fail->pp; } void prepare() { node *p; node *q; int i,j; memset(a,0,sizeof(a)); for(i=1;i<=tot+1;i++)a[i][tot+1]=1; for(i=1;i<=tot;i++){ for(j=0;j<=25;j++){ p=ac[i]; if(p->son[j]!=NULL)p=p->son[j]; else{ q=p->fail; while(q!=NULL){ if(q->son[j]!=NULL){ p=q->son[j]; break; } q=q->fail; } if(q==NULL)p=root; } if(p->pp==true)a[i][p->num]++; } } } void mi(int x,int mx) { int i,j,k; if(x==1)return; mi(x/2,mx); for(i=1;i<=mx;i++){ for(j=1;j<=mx;j++){ c[i][j]=0; for(k=1;k<=mx;k++)c[i][j]=c[i][j]+a[i][k]*a[k][j]; } } for(i=1;i<=mx;i++) for(j=1;j<=mx;j++)a[i][j]=c[i][j]; if(x%2==1){ for(i=1;i<=mx;i++){ for(j=1;j<=mx;j++){ c[i][j]=0; for(k=1;k<=mx;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]; } } for(i=1;i<=mx;i++) for(j=1;j<=mx;j++)a[i][j]=c[i][j]; } } void work() { int i,j,li; mus=0; for(i=1;i<=tot+1;i++) for(j=1;j<=tot+1;j++)b[i][j]=a[i][j]; mi(m,tot+1); for(i=1;i<=tot+1;i++)mus+=a[1][i]; b[1][1]=26; b[1][2]=0; b[2][1]=1; b[2][2]=1; a[1][1]=26; a[1][2]=0; a[2][1]=1; a[2][2]=1; mi(m,2); xzq=a[1][1]+a[2][1]; xzq-=mus; } int main() { while(scanf("%d%d",&n,&m)!=EOF){ tot=0; root=new node(); root->num=++tot; ac[tot]=root; for(i=1;i<=n;i++){ len=0; Read(); add(); } bfs(); prepare(); work(); cout<<xzq<<endl; } }