第一次写这类题...懵
直接计算答案不好计算，所以补集转化求不合法的方案。
首先考虑朴素的DP，设$f(i, s)$表示前$i$个字符，字符串为$s$的方案数，且任意一个给定串都不存在$s$中。
我们知道在一个字符串里找其他的字符串是AC自动机的强项，那么我们就可以考虑在AC自动机上跑DP，每次$+j$都在AC自动机上匹配，如果匹配到单词结尾的话就不能转移，否则就是可以转移的。
所以设$f(i, j)$为前$i$个字符，当前匹配到AC自动机上第$j$个节点的方案数，如果沿着fail一直往上的所有节点都不是单词结尾就可以转移了。
注意是大写字母T_T
#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>#define MOD(x) ((x)>=mod?(x)-mod:(x))#define ll long longusing namespace std;const int maxn=6010, maxm=110, mod=10007;struct poi{int nxt[26], fail;}tree[maxn*maxm];int n, m, ans, tott;int f[maxm][maxn], h[maxn];bool cnt[maxn];char s[maxm];inline void read(int &k){ ???int f=1; k=0; char c=getchar(); ???while(c<‘0‘ || c>‘9‘) c==‘-‘&&(f=-1), c=getchar(); ???while(c<=‘9‘ && c>=‘0‘) k=k*10+c-‘0‘, c=getchar(); ???k*=f; ???} inline void insert(){ ???int len=strlen(s+1), now=0; ???for(int i=1, ch;i<=len;i++) ???{ ???????if(!tree[now].nxt[ch=s[i]-‘A‘]) ????????tree[now].nxt[ch]=++tott; ???????now=tree[now].nxt[ch]; ???} ???cnt[now]=1;}inline void getfail(){ ???int front=1, rear=0; tree[0].fail=-1; ???for(int i=0, too;i<26;i++) ????if((too=tree[0].nxt[i])) h[++rear]=too; ???while(front<=rear) ???{ ???????int now=h[front++]; ???????for(int i=0, too;i<26;i++) ???????if((too=tree[now].nxt[i])) ????????tree[too].fail=tree[tree[now].fail].nxt[i], h[++rear]=too; ???????else tree[now].nxt[i]=tree[tree[now].fail].nxt[i]; ???????cnt[now]|=cnt[tree[now].fail]; ???}}int main(){ ???read(n); read(m); ???for(int i=1;i<=n;i++) scanf("%s", s+1), insert(); ???getfail(); f[0][0]=1; ???for(int i=1;i<=m;i++) ???for(int j=0;j<=tott;j++) ???if(!cnt[j]) for(int k=0;k<26;k++) ???f[i][tree[j].nxt[k]]=MOD(f[i][tree[j].nxt[k]]+f[i-1][j]); ???for(int i=0;i<=tott;i++) if(!cnt[i]) ans=MOD(ans+f[m][i]); ???int tot=1; for(int i=1;i<=m;i++) tot=1ll*tot*26%mod; ???printf("%d\n", MOD(tot-ans+mod));}bzoj1030: [JSOI2007]文本生成器（AC自动机+DP）
原文地址：https://www.cnblogs.com/Sakits/p/8448419.html