AC自动机与dp
前言：
本篇题解隶属于https://www.cnblogs.com/linghusama/p/17742870.html部分
首先一定要理解fail跳的原理，不然很难理解第二维为什么要设置。
首先给出大致的雏形，dp_i_j表示目前拼凑出长度为i的字符串，且ac自动机上的指针在j位置时的字符串方案数。
适用题型：
对于求必须包含、不包含某些模式串，且长度一定的合法字符串数量
以下以模版题[JSOI2007] 文本生成器为例子。
容斥原理部分不再赘述。
这里我用dp三大组成部分分别进行考虑
对于状态设计
最基础的就是两个维度，一个表示做了多长的字符串，一个表示此时自动机的位置。
对于转移：
我们考虑怎么转移到i+1这个情况上来。
首先因为加了一个新的字符，我们设它为c，那么按照自动机而言，他会先在j这个位置搜索j的儿子一圈看看能不能匹配到c。
然后我们分类讨论一下转移的思路。
- 如果找到了c就是他的儿子的话，而且c是作为一个模式串的结尾，那么就说明不能填充c这个东西。
- 如果找到了c就是他的儿子的话，而且c不是任何一个模式串的结尾，那么填充了c还是能保证不会生成出模式串，所以可以填充。
- 如果没有找到c是他的儿子的话，那么现在我要跳fail去找，此时j进行了变化，然后继续重新分类讨论。
- 如果fail跳不动了（到根节点了）,说明这么多种情况一个都没有用，全部都不合法，为0。
对于第四点，我们可以发现，如果一个节点必须要跳fail时而且fail无解时，自己也无解，这里可以在build时递归处理。
具体怎么做，我们先把不合法转移，也就是下一次会转移到模式串尾巴的地方给打上标记，所有能跳到这个位置的就利用或运算来解决
对于初始化：
为了便于决定第一个位置的c该怎么取，可以让第0位的方案数为1，便于计算。
例题代码：
#include<bits/stdc++.h>
using namespace std;
int tree[30006][30];
int cnt=0;
const int mod=1e4+7;
bool nosol[6500];
int fail[6500];
void add(string s){
int sz=s.size();
int p=0;
for(int i=0;i<sz;i++){
int c=s[i]-'A';
if(!tree[p][c]){
cnt++;
tree[p][c]=cnt;
}
p=tree[p][c];
}
nosol[p]=1;
}
void build(){
queue<int>q;
for(int i=0;i<26;i++){
if(tree[0][i]){
q.push(tree[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tree[u][i]){
fail[tree[u][i]]=tree[fail[u]][i];
nosol[tree[u][i]]|=nosol[fail[tree[u][i]]];//一个不合法全部不合法。
q.push(tree[u][i]);
}
else{
tree[u][i]=tree[fail[u]][i];
}
}
}
}
int dp[105][6500];
int qpow(int a,int b){
int ret=1;
a%=mod;
while(b){
if(b%2==1){
ret=ret*a%mod;
}
b/=2;
a=a*a%mod;
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
int n,m;
cin >> n >>m;
for(int i=1;i<=n;i++){
string s;
cin >>s;
add(s);
}
build();
// cout<<tree[2][1];
dp[0][0]=1;
for(int i=0;i<=m-1;i++){
for(int j=0;j<=cnt;j++){
for(int c=0;c<=25;c++){
if(!nosol[tree[j][c]]){
dp[i+1][tree[j][c]]=(dp[i+1][tree[j][c]]+dp[i][j])%mod;
}
}
}
}
int ans=qpow(26,m);
// cout<<ans<<endl;
for(int i=0;i<=cnt;i++)
ans=(ans-dp[m][i]+mod)%mod;
cout<<ans;
}