记录编号	378493	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1676]文本生成器	最终得分	100
用户昵称	yourfather	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2017-03-04 08:48:55	内存使用	0.37 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define mod 10007
const int maxn = 80;
int ch[maxn][26]={0},fail[maxn]={0},dan[maxn]={0};
int N,M,q[maxn],front = -1,back = 0,node = 0;
char str[maxn]={0};
struct  Matrix{
	int num[maxn][maxn];
	Matrix(){memset(num,0,sizeof num);}
	Matrix operator * (const Matrix &a)const{
		Matrix c;
		for(int i = 0;i <= node;i++)
		for(int j = 0;j <= node;j++){
			for(int k = 0;k <= node;k++)c.num[i][j] += num[i][k]*a.num[k][j]%mod;
			c.num[i][j] %= mod;
		}
		return c;
	}
}E,I,A;
void Insert(char *r){
	int n = strlen(r),now = 0;
	for(int i = 0;i < n;i++){
		if(!ch[now][r[i]-'A'])ch[now][r[i]-'A'] = ++node;
		now = ch[now][r[i]-'A'];
	}
	dan[now] = true;
}
void GetFail(){
	for(int i = 0;i < 26;i++)
		if(ch[0][i])q[++front] = ch[0][i];
	while(back <= front){
		int now = q[back++];
		for(int i = 0;i < 26;i++){
			int u = ch[now][i];
			if(!u){ch[now][i] = ch[fail[now]][i];continue;}
			q[++front] = u;
			if(dan[now])dan[u] = true;
			int temp = fail[now];
			while(temp && !ch[temp][i])temp = fail[temp];
			temp = ch[temp][i];
			fail[u]  = temp;
			if(dan[temp])dan[u] = true;
		}
	}
}
void Build(){
	for(int i = 0;i <= node;i++)if(!dan[i]){
		for(int j = 0;j < 26;j++)if(!dan[ch[i][j]]){
			A.num[ch[i][j]][i] += 1;
		}
	}
}
Matrix qpow(Matrix x,int len){
	for(;len;len >>= 1){
		if(len & 1)E = E*x;
		x = x*x;
	}
	return E;
}
int qpow(int x,int len){
	int ret = 1;
	for(;len;len>>=1){
		if(len&1)ret = ret*x % mod;
		x = x*x % mod;
	}
	return ret;
}
int main(){
	freopen("textgen.in","r",stdin);
	freopen("textgen.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i = 1;i <= N;i++){
		scanf("%s",str);
		Insert(str);
	}
	GetFail();
	for(int i = 0;i <= node;i++)E.num[i][i] = 1;
	for(int i = 0;i <= node;i++)I.num[1][i] = 1;
	Build();
	
	I = I * qpow(A,M);
	int ans = qpow(26,M) - I.num[1][0];
	ans = (ans % mod+mod)%mod;
	printf("%d",ans);
	return 0;
}