2021.11.11 P4052 [JSOI2007]文本生成器（AC自动机+DP）

https://www.luogu.com.cn/problem/P4052

题意：

JSOI 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 v6 版。

该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 s 包含单词 t，当且仅当单词 t 是文章 s 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？

答案对 10^4 + 7 取模。

分析：

长度为m的字符串一共有 \(26^m\) 种不同的排列，根据容斥原理，我们可以求出有多少字符串没有出现这n个字符串中任意一个，结果一减就行。

大部分 \(f[i][j]\) 表示当前在节点j,且串长为i时的情况，

有时再加一维表示这个状态里面包含了哪些东西，

而且AC自动机的DP会经常让你用矩阵乘法优化

来自https://www.luogu.com.cn/blog/Refun/solution-p4052

如果长度为i判断到 \(t[j][k]\) 时不是终点，那么 \(f[i][t[i][k]]\) 可以由 \(f[i-1][j]\) 转移过来。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int N=110;

const int M=65;

const int mod=1e4+7;

int n,m;

char s[101];

struct node{

	int t[6001][26],fail[6001],endi[6001],f[101][6001],tot;

	queue<int>q;

	inline void insert(char *s){

		int len=strlen(s),u=0;

		for(int i=0;i<len;i++){

			int v=s[i]-'A';

			if(!t[u][v])t[u][v]=++tot;

			u=t[u][v];

		}

		endi[u]=1;

	}

	inline void build(){

		for(int i=0;i<26;i++)if(t[0][i])q.push(t[0][i]);

		while(!q.empty()){

			int u=q.front();q.pop();

			for(int i=0;i<26;i++){

				if(t[u][i]){

					fail[t[u][i]]=t[fail[u]][i];

					endi[t[u][i]]|=endi[t[fail[u]][i]];

					q.push(t[u][i]);

				}else t[u][i]=t[fail[u]][i];

			}

		}

	}

	inline void solve(){

		f[0][0]=1;

		for(int i=1;i<=m;i++)

		for(int j=0;j<=tot;j++)

		for(int k=0;k<26;k++)

		if(!endi[t[j][k]])f[i][t[j][k]]=(f[i][t[j][k]]+f[i-1][j])%mod;

		int ans=1;

		for(int i=1;i<=m;i++)ans=(ans*26)%mod;

		for(int i=0;i<=tot;i++)ans=(ans-f[m][i]+mod)%mod;

		cout<<ans;

	}

}trie;

int main(){

	cin>>n>>m;

	for(int i=1;i<=n;i++)scanf("%s",s),trie.insert(s);

	trie.build();

	trie.solve();

	return 0;

}