文本生成器加强版 （吐槽）

感觉没有什么加强。 这个题单纯的增加m大小，而在AC自动机中的节点个数还依旧是大约6000个，所以依旧不能使用矩阵快速幂进行优化，就正常的计算即可。 同样是通过暴力枚举，进行dp出来不存在这写字符串的数的个数，然后使用总数减去。 注意AC自动机建完之后，用fail拓扑序来进行一次递推。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std ;

using ll = long long ;
using pii = pair<int,int> ;

const int N = 6100 ;
const int mod = 10007 ;

int n,m ;
char s[N] ;
int f[2][N] ;  // dp的滚动数组

namespace Acam{  // Ac自动机
	int tr[N][26],ne[N],idx ;
	int q[N] ;
	bool st[N] ;

	void insert(char s[]){
		int p = 0 ;
		for(int i = 1 ; s[i] ; i ++){
			int x = s[i] - 'A' ;
			if(!tr[p][x]) tr[p][x] = ++ idx ;
			p = tr[p][x] ;
		}
		st[p] = 1 ;
	}

	void build(){
		int hh = 0,tt = -1;
		for(int i = 0 ; i < 26 ; i ++)
			if(tr[0][i]) q[++tt] = tr[0][i] ;

		while(hh <= tt){
			int t = q[hh++] ;

			for(int i = 0 ; i < 26; i ++){
				int j = tr[t][i] ;
				if(!j) tr[t][i] = tr[ne[t]][i] ;
				else{
					ne[j] = tr[ne[t]][i] ;
					q[++tt] = j ;
				}
			}
		}

		for(int i = 0 ; i <= tt ; i ++)  // 这里就是按照拓扑序进行向下递推
			st[q[i]] |= st[ne[q[i]]] ;
	}
}

int main(){
	scanf("%d%d",&n,&m) ;

	for(int i = 1 ; i <= n ; i ++){
		scanf("%s",s+1) ;
		Acam::insert(s) ;
	}
	Acam::build() ;

	f[0][0] = 1 ;
	int ans = 1 ;
	for(int i = 1 ; i <= m ; i ++){
		for(int pre = 0 ; pre <= Acam::idx ; pre ++) f[i&1][pre] = 0 ;
		for(int pre = 0 ; pre <= Acam::idx ; pre ++){ // 枚举节点
			if(Acam::st[pre]) continue ;  // 这里会加快算法运行
			for(int c = 0 ; c < 26 ; c ++){  // 枚举下一个选什么
				int nx = Acam::tr[pre][c] ;

				if(Acam::st[nx]) continue ;
				f[i&1][nx] += f[i&1^1][pre] ; // 状态转移
				if(f[i&1][nx] > mod) f[i&1][nx] -= mod ;
			}
		}
		ans = ans * 26 % mod ;
	}

	for(int i = 0 ; i <= Acam::idx ; i ++) ans = (ans - f[m&1][i]) % mod ;
	printf("%d\n",(ans + mod) % mod) ;
	return 0 ;
}