记录编号	85246	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1676]文本生成器	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2013-12-30 20:08:51	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef unsigned ll;
const ll MOD=10007;
const int SIZEN=11;
const int SIZES=62;
string dict[SIZEN];
int stpos[SIZEN]={0};//字符串的状态编号起点
int maxmatch[SIZEN]={0};//每个单词有意义状态的最大下标
int N,SNUM;//SNUM为状态数
int L;
pair<int,int> state[SIZES];//将所有"某个单词的某个前缀"压缩成一维.state[i]的first储存在dict中的下标,second储存在字符串中的下标,特别的1为空串
class MATRIX{
public:
	int n,m;//n行m列
	ll s[SIZES][SIZES];
	MATRIX(){//初始化为零
		m=n=0;
		memset(s,0,sizeof(s));
	}
	void print(void){//调试接口,输出矩阵
		cout<<"size:"<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) cout<<s[i][j]<<" ";
			cout<<endl;
		}
	}
	void assign_one(int sn){//赋值为sn行的单位矩阵
		n=m=sn;
		for(int i=1;i<=n;i++) s[i][i]=1;
	}
};
MATRIX operator * (MATRIX a,MATRIX b){//矩阵乘法,结果对MOD取模
	MATRIX c;
	c.n=a.n;c.m=b.m;
	int i,j,k;
	for(i=1;i<=c.n;i++){
		for(j=1;j<=c.m;j++){
			c.s[i][j]=0;
			for(k=1;k<=a.m;k++){
				c.s[i][j]+=(a.s[i][k]*b.s[k][j]);
			}
			c.s[i][j]%=MOD;
		}
	}
	return c;
}
MATRIX quickpow(MATRIX a,ll n,int sn){//a^n,sn行/列
	MATRIX ans;ans.assign_one(sn);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
ll quickpow(ll x,ll y){//x^y%MOD
	ll ans=1;
	ll temp=x;
	while(y){
		if(y&1) ans=ans*temp%MOD;//奇数
		temp=temp*temp%MOD;
		y>>=1;
	}
	return ans;
}
int pairpos(pair<int,int> p){//第x个字符串下标为y的状态编号
	return stpos[p.first]+p.second;
}
int findprefix(string str,int k){//得到str长度为k的后缀是哪个单词的前缀
	int start,i,j;
	start=str.size()-k;
	for(i=1;i<=N;i++){
		if(dict[i].size()<k) continue;
		for(j=0;j<k;j++) if(str[start+j]!=dict[i][j]) goto NEXT;
		if(j==dict[i].size()||j-1>maxmatch[i]) return -1;//单词被完全匹配
		return i;
		NEXT:;
	}
	return 0;//若无合适的前缀就是第0号单词(空串)
}
int match(string str){//得到"最大匹配"的标号
	pair<int,int> ans=make_pair(0,0);//first是单词,second是到第几个下标
	int i,j;
	bool flag=false;
	for(i=str.size();i>=1;i--){
		j=findprefix(str,i);
		if(j==-1) return 0;//完全匹配,无效
		if(j){
			ans=make_pair(j,i-1);
			break;
		}
	}
	return pairpos(ans);
}
bool read(void){
	if(scanf("%d%d",&N,&L)==EOF) return false;
	int i;
	for(i=1;i<=N;i++) cin>>dict[i];
	return true;
}
void init(MATRIX &G,MATRIX &D){
	int i,j,k,t,st,tot=1;
	string str;
	state[tot]=make_pair(0,-1),stpos[0]=tot,maxmatch[0]=-1;
	dict[0]="\0";
	for(i=1;i<=N;i++){
		stpos[i]=tot+1;
		str="\0";
		maxmatch[i]=dict[i].size()-2;//若没有其他因素,一直到'少一个'都是有意义的状态
		for(j=0;j<dict[i].size()-1;j++){//不能出现完全匹配某单词的状态
			str+=dict[i][j];
			for(k=1;k<=N;k++){
				for(t=0;t<dict[k].size();t++){
					if(dict[k][dict[k].size()-1-t]!=str[str.size()-1-t]) break;
				}
				if(t==dict[k].size()){
					maxmatch[i]=j-1;
					goto NEXT;
				}
			}
			state[++tot]=make_pair(i,j);
		}
		NEXT:;
	}
	SNUM=tot;
	G.n=1,G.m=SNUM;
	for(i=1;i<=SNUM;i++) G.s[1][i]=1;//初始化了G
	D.n=D.m=SNUM;
	for(i=1;i<=SNUM;i++){
		str="\0";
		for(j=0;j<=state[i].second;j++) str+=dict[state[i].first][j];
		for(j=0;j<26;j++){//枚举26个字母
			k=match(str+char(j+'A'));
			if(k) D.s[k][i]++;
		}
	}
}
void work(void){
	MATRIX G,D;//G是状态矩阵,D是转移矩阵
	init(G,D);
	G=G*quickpow(D,L,SNUM);
	ll ans=quickpow(26,L)-G.s[1][1];
	cout<<(ans+MOD)%MOD<<endl;
}
int main(){
	freopen("textgen.in","r",stdin);
	freopen("textgen.out","w",stdout);
	while(read()) work();
	return 0;
}