[文章目录]
Description
该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？
我们构想一下哪一个随机的串上单词里跑AC，如果这个串里有单词，那肯定是有一次匹配到了单词的末尾节点或是危险节点（一开始忘记考虑危险节点了XwX）。那么，我们就可以每次将trie树扫一遍，让每个节点的串数量随机跑到下一个节点，遇到危险节点就不跑了。然后统计一下扫了m次之后，仍然存活的串的数目，拿总数减去就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod=10007;
int n,m,fna;
char st[120];
struct trie
{
trie *ch[26],*fail;
int ans[2];bool flag;
trie()
{
memset(ch,0,sizeof(ch));
fail=NULL;ans[0]=ans[1]=0;flag=0;
}
}*root=new trie();
void Free(trie* x)
{
if(!x) return ;
for(int i=0;i<26;i++) Free(x->ch[i]);
free(x);
}
void insert()
{
int len=strlen(st+1);
trie *p=root;
for(int i=1;i<=len;i++)
{
if(!p->ch[st[i]-'A']) p->ch[st[i]-'A']=new trie();
p=p->ch[st[i]-'A'];
if(p->flag) break;
}
p->flag=1;
}
void build_ac_auto()
{
static trie* q[60000];
int l=1,r=0;
for(int i=0;i<26;i++)
if(root->ch[i])
root->ch[i]->fail=root,
q[++r]=root->ch[i];
while(l<=r)
{
trie* p=q[l++];
for(int i=0;i<26;i++)
if(p->ch[i])
{
trie* tmp=p->fail;
while(tmp!=root&&!tmp->ch[i]) tmp=tmp->fail;
if(tmp->ch[i]) tmp=tmp->ch[i];
p->ch[i]->fail=tmp;
q[++r]=p->ch[i];
}
}
root->fail=root;
for(int i=1;i<=r;i++) if(q[i]->fail->flag) q[i]->flag=1;
l=1,r=0;q[++r]=root;
while(l<=r)
{
trie* p=q[l++];
for(int i=0;i<26;i++)
if(p->ch[i]&&!p->ch[i]->flag)
q[++r]=p->ch[i];
}
root->ans[0]=1;
bool flag=1;
while(m--)
{
for(int i=1;i<=r;i++)
q[i]->ans[flag]=0;
for(int i=1;i<=r;i++)
{
if(!q[i]->flag&&q[i]->ans[flag^1])
{
for(int j=0;j<26;j++)
if(q[i]->ch[j]) q[i]->ch[j]->ans[flag]=(q[i]->ch[j]->ans[flag]+q[i]->ans[flag^1])%mod;
else
{
trie* tmp=q[i]->fail;
while(tmp!=root&&!tmp->ch[j]) tmp=tmp->fail;
if(tmp->ch[j]) tmp=tmp->ch[j];
tmp->ans[flag]=(tmp->ans[flag]+q[i]->ans[flag^1])%mod;
}
}
}
flag^=1;
}
flag^=1;
for(int i=1;i<=r;i++)
if(!q[i]->flag) fna=(fna+q[i]->ans[flag])%mod;
}
int pow(int x,int y)
{
int re=1;
while(y)
{
if(y&1) re=re*x%mod;
y>>=1; x=x*x%mod;
}
return re;
}
int main()
{
scanf("%d%d",&n,&m);
int c=m;
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
insert();
}
build_ac_auto();
printf("%d",(pow(26,c)-fna+mod)%mod);
return 0;
}