记录编号	122559	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1676]文本生成器	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.090 s
提交时间	2014-09-24 08:27:49	内存使用	236.87 MiB

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
#define CL(x) memset(x,0,sizeof(x))
using namespace std;
const int MOD=10007;
const int MAXM=1e6+10;
const int MAXN=60+2;
const int MAXC=26;
inline int IDX(char c){ return c-'A'; }
struct mat{
	int a[MAXN][MAXN];
	int n,m;
	void init(int n=0,int m=0){ 
		this->n=n; this->m=m;
		memset(a,0,sizeof(a));
	}
	void init_e(int len){
		init(len,len);
		for(int i=1;i<=len;i++)a[i][i]=1;
	}
	mat(){ init(); }
	
	mat operator * (const mat &  mm)const{
		mat ret;
		ret.init(n,mm.m);
		for(int i=1;i<=ret.n;i++)for(int j=1;j<=ret.m;j++){
			int tmp=0;
			for(int k=1;k<=m;k++){
				tmp+=a[i][k]*mm.a[k][j];
				tmp%=MOD;
			}
			ret.a[i][j]=tmp;
		}
		return ret;
	}
	
	void print(){
		printf("%d %d\n",n,m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
	}
};
mat pow(mat d,int k){
	mat ret;
	if(k==0){
		ret.init_e(d.n);
		return ret;
	}
	ret=pow(d,k/2);
	ret=ret*ret;
	if(k%2) ret=ret*d;
	return ret;
}
struct AcAutoMachine{
	int son[MAXN][MAXC], fail[MAXN], last[MAXN];
	int val[MAXN];
	int node_cnt;
	void init(){
		node_cnt=0;
		CL(son[0]); CL(fail); CL(last);
		CL(val);
	}
	AcAutoMachine(){ init(); }
	int new_node(){
		int idx=++node_cnt;
		CL(son[idx]);
		return idx;
	}
	void insert(char str[]){
		int u=0;
		for(int i=0;str[i];i++){
			int c=IDX(str[i]);
			if(son[u][c]==0)
				son[u][c]=new_node();
			u=son[u][c];
		}
		val[u]++;
	}
	void build(){
		queue<int> q; q.push(0);
		while(q.size()){
			int u=q.front(); q.pop();
			for(int c=0;c<MAXC;c++){
				int v=son[u][c];
				if(v==0)continue;
				q.push(v);
				
				if(u==0) continue;
				int t=fail[u];
				while(son[t][c]==0 && t!=0)
					t=fail[t];
				if(son[t][c])
					t=son[t][c];
				fail[v]=t;
				last[v]= val[t] ? t:last[t];
			}
		}
	}
}solver;

int N,M;
void init(){
	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;i++){
		char tmp_str[MAXN]={0};
		scanf("%s",&tmp_str);
		solver.insert(tmp_str);
	}
	solver.build();
}
int F[MAXM][MAXN];
bool val[MAXN];
int next[MAXN][MAXC]; 
mat CH,D;
void work(){
	F[0][0]=1;
	int node_cnt=solver.node_cnt;
	
	for(int j=0;j<=node_cnt;j++){
		if(solver.val[j] || solver.last[j]) val[j]=true;
		for(int c=0;c<MAXC;c++){
			int t=j;
			while(solver.son[t][c]==0 && t!=0)
				t=solver.fail[t];
			if(solver.son[t][c])
				t=solver.son[t][c];
			next[j][c]=t;
		}
	}
	
	D.n=node_cnt+1;
	D.m=1;
	D.a[1][1]=1;
	
	CH.n=CH.m=node_cnt+1;
	for(int j=0;j<=node_cnt;j++){
		if(val[j])continue;
		for(int c=0;c<MAXC;c++){
			int v=next[j][c];
			if(val[v])continue;
			CH.a[v+1][j+1]++;
		}
	}
	//CH.print();
	CH=pow(CH,M);
	D=CH*D;
	
	//D.print();
	
	/*
	for(int i=0;i<M;i++){
		for(int j=0;j<=node_cnt;j++){
			if(val[j]) continue;
			//if(F[i][j]==0)continue;
			for(int c=0;c<MAXC;c++){
				int t=next[j][c];
				if(val[t])continue;
				F[i+1][t]+=F[i][j];
				//F[i+1][t]%=MOD;
			}
		}
		
		if(i%2==0 && i!=M-1)continue;
		for(int j=0;j<=node_cnt;j++){
			F[i+1][j]%=MOD;
		}
		
	}*/
	
	int tot=1,ans=0;
	for(int i=1;i<=M;i++)
		tot*=MAXC ,tot%=MOD;
	for(int j=1;j<=node_cnt+1;j++)
		ans+=D.a[j][1], ans%=MOD;
	ans=tot+MOD-ans;
	ans%=MOD;
	printf("%d\n",ans);
}
int main(){
	freopen("textgen.in","r",stdin);
	freopen("textgen.out","w",stdout);
	//freopen("in.txt","r",stdin);
	init();
	work();
	//while(true);
	return 0;
}