BZOJ.1030.[JSOI2007]文本生成器(AC自动机 DP)

题目链接
洛谷

直接在AC自动机上DP。
\(f[i][j]\)表示 当前是文本第 \(i\)位，匹配到了AC自动机上的 \(j\)节点 此时的文章数。
转移时就枚举26个字母，转移到AC自动机上的下一个节点。
任意匹配一个单词就可以，所以当前节点 \(j\) 如果是模式串的结束节点，不再跳到下一个节点，而是直接*26给 \(f[i+1][j]\)。
不是结束节点的话 跳到下一个节点直接加上。

注意一个节点如果能通过fail指针跳到模式串的结束节点，那么它也是一个结束节点。。已经忘了。
容斥去算不满足条件的文本数量也可以。不过我这么做好像常数更优233.

//3900kb	68ms
#include 
#include 
#include 
#include 
#define mod (10007)
#define gc() getchar()
const int N=6e3+7;

int n,num,tot,f[103][N];
char s[105];
struct AC_Automaton
{
	int tot,son[N][26],fail[N],q[N];
	bool val[N];

	void Insert(char *s)
	{
		int l=strlen(s),x=0;
		for(int id,i=0; i