[JSOI2007]文本生成器

解题思路

题目要求求出包含至少一个串的方案

考虑用总方案\(26^M\)减去不包含的方案

将给定\(N\)个串建出AC自动机

定义危险结点为该节点 在Trie上代表的串 包含了给定串中某个

由fail树的性质可知,这类结点出现且仅出现在某个结尾结点fail树上的子树内

然后就可以dp了

定义\(dp[i][j]\)为放了前\(i\)个字符,匹配到了自动机上的j结点

增加一个字符就是走到\(j\)在自动机上的某个儿子,但是要避免走到危险结点(即不转移下去)

统计答案就是\(\sum dp[M][j]\),即加入M个字符后不在危险结点的方案数(即使途中经过也已经在dp时去掉了)

#include<iostream>#include<cstdio>#include<queue>const int P=10007;struct AC_automaton{ struct node{ int son[26]; int fail; bool dg; }T[100000]; int tot; void insert(std::string &S){ int len=S.length(),now=0; for (int i=0;i<len;i++){ int &nxt=T[now].son[S[i]-‘A‘]; if (!nxt) nxt=++tot; now=nxt; } T[now].dg=true; } void build(){ std::queue<int> Q; for (int i=0;i<26;i++) if (T[0].son[i]) Q.push(T[0].son[i]); while (!Q.empty()){ int now=Q.front(); Q.pop(); T[now].dg|=T[T[now].fail].dg; for (int i=0;i<26;i++){ if (T[now].son[i]) T[T[now].son[i]].fail=T[T[now].fail].son[i],Q.push(T[now].son[i]); else T[now].son[i]=T[T[now].fail].son[i]; } } }}AC;int n,M;std::string S;int dp[101][6001],Ans;inline void chkadd(int &a,int b){a+=b;if (a>=P) a-=P;}int fast_pow(int a,int b){ int ret=1; for (b<<=1;b>>=1;a=a*a%P) if (b&1) ret=ret*a%P; return ret;}int main(){ scanf("%d%d",&n,&M); for (int i=1;i<=n;i++) std::cin>>S,AC.insert(S); AC.build(); dp[0][0]=1; for (int i=1;i<=M;i++){ for (int j=0;j<=AC.tot;j++){ if (AC.T[j].dg) continue; for (int k=0;k<26;k++) chkadd(dp[i][AC.T[j].son[k]],dp[i-1][j]); } } for (int i=0;i<=AC.tot;i++){ if (AC.T[i].dg) continue; chkadd(Ans,dp[M][i]); } printf("%d\n",(fast_pow(26,M)-Ans+P)%P);}

相关文章