【传送门：BZOJ1030】
简要题意：
给出n个单词，要求求出至少含一个单词的长度为n的字符串数量
题解：
显然直接求出是很难求的，那么我们就求出总的字符串数量，再求出不含任何一个单词的字符串数量
然后相减就是答案
很像GT考试，不过变成了多个串，那么就用AC自动机
设f[i][j]为长度为i时到达字典树上第j个点的不含任何一个单词的字符串数量
只要保证该状态合理就可以继承了
参考代码：
#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>using namespace std;int Mod=10007;struct trie{ ???int c[27],s,fail;}t[11000];int tot,root;void clean(int x){ ???memset(t[x].c,-1,sizeof(t[x].c)); ???t[x].s=0;}char st[110];void bt(){ ???int x=0,len=strlen(st+1); ???for(int i=1;i<=len;i++) ???{ ???????int y=st[i]-‘A‘+1; ???????if(t[x].c[y]==-1) clean(++tot),t[x].c[y]=tot; ???????x=t[x].c[y]; ???} ???t[x].s=1;}int list[11000];void bfs(){ ???list[1]=0; ???int head=1,tail=1; ???while(head<=tail) ???{ ???????int x=list[head]; ???????for(int i=1;i<=26;i++) ???????{ ???????????int son=t[x].c[i]; ???????????if(son==-1) continue; ???????????if(x==0) t[son].fail=0; ???????????else ???????????{ ???????????????int j=t[x].fail; ???????????????while(j!=0&&t[j].c[i]==-1) j=t[j].fail; ???????????????t[son].fail=max(0,t[j].c[i]); ???????????????if(t[t[son].fail].s==1) t[son].s=1; ???????????} ???????????list[++tail]=son; ???????} ???????head++; ???}}int f[110][11000];int main(){ ???int n,m; ???scanf("%d%d",&n,&m); ???tot=0;clean(0); ???for(int i=1;i<=n;i++) ???{ ???????scanf("%s",st+1); ???????bt(); ???} ???bfs(); ???memset(f,0,sizeof(f)); ???int sum=1; ???for(int i=1;i<=m;i++) sum=(sum*26)%Mod; ???f[0][0]=1; ???for(int u=1;u<=m;u++) ???{ ???????for(int i=0;i<=tot;i++) ???????{ ???????????if(t[i].s==0&&f[u-1][i]>0) ???????????{ ???????????????for(int j=1;j<=26;j++) ???????????????{ ???????????????????int k=i; ???????????????????while(k!=0&&t[k].c[j]==-1) k=t[k].fail; ???????????????????int son=t[k].c[j]; ???????????????????if(son==-1) son=0; ???????????????????f[u][son]=(f[u][son]+f[u-1][i])%Mod; ???????????????} ???????????} ???????} ???} ???int ans=0; ???for(int i=0;i<=tot;i++) if(t[i].s==0) ans=(ans+f[m][i])%Mod; ???printf("%d\n",((sum-ans)%Mod+Mod)%Mod); ???return 0;}BZOJ1030: [JSOI2007]文本生成器
原文地址：https://www.cnblogs.com/Never-mind/p/8955149.html