门
记住常见DP+ACM的套路：$dp_{i,j}$表示长度i,节点j,可能多加一维表示状态

题目

长度为m的最少包含一个模式串的文本串的方案数

题解

AC自动机建好后思考dp转移
$dp_{i,j，0/1}$表示长度为i,状态在j号节点，0/1表示是否含有模式串

如果j为终止节点
$dp_{i,j,1}=\sum dp_{i,k,1}+dp_{i,k,0}$
否则
$dp_{i,j,1}=\sum dp_{i,k,1}$
$dp_{i,j,0}=\sum dp_{i,k,0}$

#include<bits/stdc++.h>
using namespace std;
const int N=6e3+10,K=105,mod=1e4+7;
int t[N][30],all;
int f[N];bool val[N];
void putin(char *s)
{int p=0;for(int i=0;s[i];i++){int now=s[i]-'A';if(!t[p][now])t[p][now]=++all;p=t[p][now];}val[p]=1;
}
void get_fail()
{queue<int>q;int p=0;for(int i=0;i<26;i++)if(t[p][i])q.push(t[p][i]);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<26;i++){p=t[u][i];if(!p){t[u][i]=t[f[u]][i];continue;}q.push(p);int pre=f[u];while(pre&&!t[pre][i])pre=f[pre];f[p]=t[pre][i];}val[u]|=val[f[u]];}
}
int n,k;
int dp[K][N][2];
char s[N];
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%s",s);putin(s);}get_fail();dp[0][0][0]=1;for(int i=1;i<=k;i++)for(int p=0;p<=all;p++)for(int j=0;j<26;j++){int u=t[p][j];if(val[u]){dp[i][u][1]+=dp[i-1][p][1]+dp[i-1][p][0];dp[i][u][1]%=mod;}else{dp[i][u][1]+=dp[i-1][p][1];dp[i][u][1]%=mod;dp[i][u][0]+=dp[i-1][p][0];dp[i][u][0]%=mod;}}int ans=0;for(int p=0;p<=all;p++)ans+=dp[k][p][1],ans%=mod;printf("%d\n",ans);
}