标签：AC自动机，DP，容斥原理
题目
Description
JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。
该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。
如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。
但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。
ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？
Input
输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A..Z
Output
一个整数，表示可能的文章总数。只需要知道结果模10007的值。
Sample Input
2 2
A
B
Sample Output
100
题意
给定多个模式串和M
求一个长度为M的新串，不与任何一个模式串匹配的方案数
分析
因为有多个模式串，先建立AC自动机
然后DP
f[i][j]表示当长度为i时匹配到j节点时的情况数
根据point节点转移，相当于在Trie树上DP
用容斥原理考虑否定（不可读）的情况，然后用总的方案数m^26减去否定的情况
否定的情况就是\(\sum_{i=1}^{id} f[m][i] (danger[i]不为空)\)
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=6e3+6,mod=1e4+7;
int trie[maxn][27],point[maxn],que[maxn<<2],f[106][maxn];
char st[maxn];int n,m,id=1,ans1,ans2=1;
bool danger[maxn];
void insert(){
int now=1,k,len=strlen(st+1);
rep(i,1,len){
k=st[i]-'A'+1;
if(!trie[now][k])trie[now][k]=++id;
now=trie[now][k];
}
danger[now]=1;
}
void acmach(){
int head=0,tail=1,now;
que[0]=1;point[1]=0;
while(head<tail){
now=que[head++];
rep(i,1,26){
if(!trie[now][i])continue;
int k=point[now];while(!trie[k][i])k=point[k];
point[trie[now][i]]=trie[k][i];que[tail++]=trie[now][i];
if(danger[trie[k][i]])danger[trie[now][i]]=1;
}
}
}
void dp(int x){
rep(i,1,id){
if(danger[i]||!f[x-1][i])continue;
rep(j,1,26){
int k=i;
while(!trie[k][j])k=point[k];
f[x][trie[k][j]]=(f[x][trie[k][j]]+f[x-1][i])%mod;
}
}
}
int main()
{
n=read(),m=read();
rep(i,1,26)trie[0][i]=1;
rep(i,1,n)scanf("%s",st+1),insert();
acmach();
f[0][1]=1;
rep(i,1,m)dp(i);
rep(i,1,m)ans2=(ans2*26)%mod;
rep(i,1,id)
if(!danger[i])ans1=(ans1+f[m][i])%mod;
cout<<(ans2-ans1+mod)%mod<<endl;
return 0;
}
