P4052 [JSOI2007]文本生成器

#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int mod=10007;struct data{ ???int nxt[26],fail,end;}a[6002];int n,m,cnt,ans=1,f[102][6002];char q[102];inline void Trie_build(){ ???scanf("%s",q); ???int u=0,len=strlen(q); ???for(int i=0;i<len;++i){ ???????int p=q[i]-‘A‘; ???????if(!a[u].nxt[p]) a[u].nxt[p]=++cnt; ???????u=a[u].nxt[p]; ???}++a[u].end;}inline void AC_build(){ ???queue <int> h; ???for(int i=0;i<26;++i) if(a[0].nxt[i]) h.push(a[0].nxt[i]); ???while(!h.empty()){ ???????int x=h.front(); h.pop(); ???????for(int i=0;i<26;++i){ ???????????int &to=a[x].nxt[i]; ???????????if(to){ ???????????????a[to].fail=a[a[x].fail].nxt[i]; ???????????????a[to].end|=a[a[to].fail].end; //如果该串的后缀是可识别的那么这个串也一定是可识别的 ???????????????h.push(to); ???????????}else to=a[a[x].fail].nxt[i]; ???????} ???}}int main(){ ???scanf("%d%d",&n,&m); ???for(int i=1;i<=n;++i) Trie_build(); ???AC_build(); ???f[0][0]=1; ???for(int i=1;i<=m;++i) ???????for(int j=0;j<=cnt;++j) ???????????for(int k=0;k<26;++k) ???????????????if(!a[a[j].nxt[k]].end) //不可识别 ???????????????????f[i][a[j].nxt[k]]=(f[i][a[j].nxt[k]]+f[i-1][j])%mod; ???for(int i=1;i<=m;++i) ans=ans*26%mod; ???for(int i=0;i<=cnt;++i) ans=(ans-f[m][i]+mod)%mod; //总方案数-不可识别方案数 ???printf("%d",ans); ???return 0;}