1030 - [JSOI2007]文本生成器

AC自动机+dp （bymod998244353）

用总的减去不可读的即是可读的。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6006,mod=10007;
struct trie {
	int son[26],flag,fail;
}tr[MAXN];
int n,m,tcnt,f[MAXN][MAXN];
char c[MAXN];
void insert(char*c,int len) {
	int u=1;
	for(int i=0,val; i<len; ++i) {
		val=c[i]-'A';
		u=tr[u].son[val]?tr[u].son[val]:tr[u].son[val]=++tcnt;
	}
	tr[u].flag=1;
}
void Fail() {
	static queue<int>q;
	while(!q.empty())q.pop();
	for(int i=0; i<26; ++i)tr[0].son[i]=1;
	tr[1].fail=0,q.push(1);
	while(!q.empty()) {
		int u=q.front(),fail=tr[u].fail;
		q.pop();
		for(int i=0,v; i<26; ++i) {
			v=tr[u].son[i];
			if(!v) {
				tr[u].son[i]=tr[fail].son[i];
				continue;
			}
			tr[v].fail=tr[fail].son[i];
			q.push(v);
			tr[v].flag|=tr[tr[fail].son[i]].flag;
		}
	}
}
inline void Getmod(int&a,int b) {
	if((a+=b)>=mod)a-=mod;
}
int fastpow(int a,int k) {
	int base=1;
	for(; k; k>>=1) {
		if(k&1)base=base*1ll*a%mod;
		a=a*1ll*a%mod;
	}
	return base;
}
int main() {
	f[0][1]=tcnt=1;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) scanf("%s",c),insert(c,strlen(c));
	Fail();
	for(int i=1; i<=m; ++i)
		for(int j=1; j<=tcnt; ++j)
			for(int k=0; k<26; ++k)
				if(!tr[tr[j].son[k]].flag)
					Getmod(f[i][tr[j].son[k]],f[i-1][j]);
	int ans=0;
	for(int i=1; i<=tcnt; ++i)Getmod(ans,f[m][i]);
	printf("%d\n",(fastpow(26,m)-ans+mod)%mod);
	return 0;
}