记录编号	367774	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1676]文本生成器	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.613 s
提交时间	2017-02-01 21:50:10	内存使用	0.88 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=210,mod=10007;
int n,l,top,go[N][26],fail[N];
char s[N];bool end[N];
struct matrix{
	int a[N][N];
	matrix(){memset(a,0,sizeof a);}
	void operator *= (const matrix x){
		matrix ans;
		for (int i=1;i<=top*2;i++)
		for (int j=1;j<=top*2;j++)
		for (int k=1;k<=top*2;k++)
			(ans.a[i][j]+=a[i][k]*x.a[k][j])%=mod;
		memcpy(a,ans.a,sizeof a);
	}
}x,ans;
matrix mi(matrix x,int y){
	matrix ans=x;y--;
	for (;y;y>>=1,x*=x)
		if (y&1) ans*=x;
	return ans;
}
void trie(){
	int len=strlen(s+1),p=1;
	for (int i=1;i<=len;i++){
		s[i]-='A';
		p=!go[p][s[i]]?go[p][s[i]]=++top:go[p][s[i]];
	}
	end[p]=1;
}
void getfail(){
	queue<int> Q;
	for (int i=0;i<26;i++)
		if (go[1][i]) Q.push(go[1][i]),fail[go[1][i]]=1;
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		for (int i=0;i<26;i++)
		if (go[v][i]){
			int u=go[v][i],now=fail[v];
			while (now&&!go[now][i]) now=fail[now];
			fail[u]=now?go[now][i]:1;
			end[u]|=end[fail[u]];
			Q.push(u);
		}
	}
	for (int v=1;v<=top;v++)
	for (int i=0;i<26;i++){
		if (!go[v][i]){
			int now=fail[v];
			while (now&&!go[now][i]) now=fail[now];
			go[v][i]=now?go[now][i]:1;
		}
		int u=go[v][i];
		x.a[v+top][u+top]++;
		x.a[v][end[u]?u+top:u]++;
	}
}
int main()
{
	freopen("textgen.in","r",stdin);
	freopen("textgen.out","w",stdout);
	top=1;
	scanf("%d%d",&n,&l);
	for (int i=1;i<=n;i++)
		scanf("%s",s+1),trie();
	getfail();
	ans.a[1][1]=1;
	ans*=mi(x,l);
	int Ans=0;
	for (int i=1;i<=top;i++)
		Ans=(Ans+ans.a[1][i+top])%mod;
	printf("%d\n",Ans);
	return 0;
}