题意
给定一些模式串，求长度为m的所有文本串的个数，且该文本串至少包括一个模式串，答案对10007取模
思路
//没有调用get_fail()调了一个小时我怕不是神仙....
看到一堆字符串的匹配问题，首先就可以考虑自动机全家桶了......很容易发现用AC自动机看起来可做
对所有串建AC自动机，然后变成trie图，一个文本串只要包括了一个end标记就说明包括至少一个串。在图上这样的统计问题，容易想到是dp
于是大多数题解到这里就运用了一个经典的四字成语
正难则反
才怪
虽然正难则反（所有串-不包含任一个的串）可做，但是按照正常的思路来说，则反首先要正难，然而它并不难......对于我这个蒟蒻来说很难就此想到反推（个人认为否定正着做会误导萌新比如本人）
用f[ i ][ j ][0 / 1]表示到了i号点，当前字符串长度为j，是否经过过有标记的点，这样的总方案数，那么最终的答案就为sigma( f[ 0 ~ ndsum ][ m ][ 1 ] )。
这样递推也是相当简单的，为了保证前一位先被求出来，所以外层循环先枚举字符串长度j
if(is_end[now])//是终点就没有0状态
{
f[now][i][1]=(f[now][i][1]+f[j][i-1][0]+f[j][i-1][1])%mod;
}
else//不是终点
{
f[now][i][0]=(f[now][i][0]+f[j][i-1][0])%mod;
f[now][i][1]=(f[now][i][1]+f[j][i-1][1])%mod;
//f[now][i][1]不从f[j][i-1][0]转化过来qwq
}
再加入AC自动机模板即可轻松切掉（）
Code：
#include<bits/stdc++.h>
#define N 6100
using namespace std;
const int mod = 10007;
int n,m;
int nxt[N][26],fail[N],is_end[N],ndsum;
int f[N][105][2];//走了j步走到了i点,是否有经过单词
char s[N];
void ad(char c[])
{
int now=0,len=strlen(c);
for(int i=0;i<len;++i)
{
int p=c[i]-'A';
if(!nxt[now][p]) nxt[now][p]=++ndsum;
now=nxt[now][p];
}
is_end[now]=1;
}
void get_fail()
{
queue<int> q;
for(int i=0;i<26;++i) if(nxt[0][i]) q.push(nxt[0][i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int j=0;j<26;++j)
{
if(nxt[u][j])
{
q.push(nxt[u][j]);
fail[nxt[u][j]]=nxt[fail[u]][j];
is_end[nxt[u][j]]|=is_end[nxt[fail[u]][j]];
}
else nxt[u][j]=nxt[fail[u]][j];
}
}
}
void dp()
{
f[0][0][0]=1;
for(int i=1;i<=m;++i)//step
{
for(int j=0;j<=ndsum;++j)//node
{
for(int k=0;k<26;++k)//next
{
int now=nxt[j][k];
if(is_end[now])//是终点就没有0状态
{
f[now][i][1]=(f[now][i][1]+f[j][i-1][0]+f[j][i-1][1])%mod;
}
else//不是终点
{
f[now][i][0]=(f[now][i][0]+f[j][i-1][0])%mod;
f[now][i][1]=(f[now][i][1]+f[j][i-1][1])%mod;
//f[now][i][1]不从f[j][i-1][0]转化过来qwq
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%s",s);
ad(s);
}
get_fail();
dp();
int ans=0;
for(int i=0;i<=ndsum;++i) ans=(ans+f[i][m][1])%mod;
printf("%d
",ans);
return 0;
}
（当然这道题f的第二维显然是可以滚掉的2333）