【题意】
给定一些单词，我们定义一篇可读文章至少包含一个这样的单词，求长度为M的可读文章总数。
【分析】
用前几题的方法可以求长度为M的不可读的文章总数Sum，所以我们可以用26^M-Sum来求出可读文章的总数。不过这题的N*Len太大，也就是AC自动机的节点太多，如果用矩阵乘法求解用爆空间，所以我直接DP了。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring> const int Maxn=;
const int Maxl=;
const int Mod=; int n,m,tot,len,total;
int q[Maxl*Maxn],f[Maxl][Maxl*Maxn];
char s[Maxl]; struct node
{
int son[],fail;
bool mark;
}t[Maxn*Maxl]; void floy()
{
tot=,total=;
memset(f,,sizeof(f));
memset(q,,sizeof(q));
for(int i=;i<=Maxl*Maxn;i++)
{
t[i].mark=;
for(int j=;j<=;j++) t[i].son[j]=;
}
} void read_trie()
{
tot=;
int i,j;
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
{
int x,ind;
scanf("%s",s+);
len=strlen(s+);
x=;
for(j=;j<=len;j++)
{
ind=s[j]-'A'+;
if(!t[x].son[ind]) t[x].son[ind]=++tot;
x=t[x].son[ind];
if(j==len) t[x].mark=;
}
}
} void build_AC()
{
int i,j,x,y;
q[++q[]]=;
for(i=;i<=q[];i++)
{
x=q[i];y=t[x].fail;
for(j=;j<=;j++)
{
if(t[x].son[j])
{
t[t[x].son[j]].fail=x?t[y].son[j]:;
if(t[t[t[x].son[j]].fail].mark) t[t[x].son[j]].mark=;
q[++q[]]=t[x].son[j];
}
else t[x].son[j]=t[y].son[j];
}
}
} void dp()
{
int i,j,k,v;
f[][]=;
for(i=;i<=m;i++)
for(j=;j<=tot;j++) if(f[i-][j])
for(k=;k<=;k++)
{
v=t[j].son[k];
if(!t[v].mark) f[i][v]=(f[i][v]+f[i-][j])%Mod;
}
for(i=;i<=tot;i++)
total=(total+f[m][i])%Mod;
} int pow(int x)
{
int ans=,sum=;
while(x)
{
if(x&) sum=(sum*ans)%Mod;
ans=(ans*ans)%Mod;
x=x>>;
}
return sum;
} int main()
{
read_trie();
build_AC();
dp();
printf("%d\n",(pow(m)-total+Mod)%Mod);
}
[BZOJ1030]
2016-07-12 10:10:32