记录编号	182203	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1676]文本生成器	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.126 s
提交时间	2015-08-27 14:18:40	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
int N,L;
string str[20];
int match[12]={0};//单词可以匹配的最大长度
int s[12][8]={0};//单词i前j被匹配时的状态编号，s[0][0]代表空串，编号为1
pair<int,int> stat[96];
int mod=10007;
int S;//总状态数
class miku
{
public:
	int s[62][62];
	int m,n;//列和行
	miku()
	{
		m=n=0;
		memset(s,0,sizeof(s));
	}
	void print()
	{
		cout<<m<<" "<<n<<endl;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			cout<<s[i][j]<<" ";
			cout<<endl;
		}
	}
	void make(int sn)
	{
		n=m=sn;
		for(int i=1;i<=n;i++)
			s[i][i]=1;
	}
}G,D;
miku operator * (miku a,miku b)
{
	miku c;
	c.n=a.n;c.m=b.m;
	for(int i=1;i<=c.n;i++)
		for(int j=1;j<=c.m;j++)
			for(int 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;		
}
inline miku quickpow(miku a,int b)
{
	miku c;
	c.make(a.n);
	//c.print();
	while(b)
	{
		if(b&1) c=c*a;
		a=a*a;b>>=1;
	}
	return c;
}
int qmi(int y)
{
	int re=1;
	int x=26;
	while(y>0)
	{
		if(y&1) re*=x;
		y>>=1;x*=x;re%=mod;x%=mod;
	}
	return re;
}
int find(string tem,int k)
{
	int start=tem.size()-k;
	int i,j;
	for(i=1;i<=N;i++)
	{
		if(str[i].size()<k) continue;
		for(j=0;j<k;j++) if(str[i][j]!=tem[start+j]) goto NEXT;
		if(j==str[i].size()||j-1>match[i]) return -1;
		return i;
		NEXT:;
	}
	return 0;
}
int mamatch(string tem)
{
	pair<int,int> ans;
	ans=make_pair(0,0);
	int j;
	for(int k=tem.size();k>=1;k--)
	{
		j=find(tem,k);
		if(j==-1) return 0;
		if(j)
		{
		ans=make_pair(j,k-1);
		break;
		}
	}
	return s[ans.first][ans.second];
}
void update()
{
	int tot=1;//当前状态的编号
	s[0][0]=tot;stat[tot]=make_pair(0,-1);match[0]=-1;
	string tem;
	for(int i=1;i<=N;i++)
	{
		tem="\0";
		match[i]=str[i].size()-2;
		for(int j=0;j<str[i].size();j++)
		{
			tem+=str[i][j];
			//cout<<tem<<endl;
			int t;
			for(int k=1;k<=N;k++)
			{
				for(t=0;t<str[k].size();t++)
				{
					if(str[k][str[k].size()-1-t]!=tem[tem.size()-1-t]) break;
				}
				if(t==str[k].size())//完全匹配
				{
					match[i]=j-1;
					goto NEXT;
					//cout<<tem<<
				}
			}
			s[i][j]=++tot;
			stat[tot]=make_pair(i,j);
			//cout<<stat[tot].first<<" "<<stat[tot].second<<" "<<tot<<endl;
		}
		NEXT:;
	}
	S=tot;
	G.n=1;G.m=S;
	//cout<<S<<endl;
	for(int i=1;i<=S;i++) G.s[1][i]=1;
	D.m=D.n=S;
	for(int i=1;i<=S;i++)
	{
		tem="\0";
		for(int j=0;j<=stat[i].second;j++) tem+=str[stat[i].first][j];
		for(int j=0;j<26;j++)
		{
		int k=mamatch(tem+char(j+'A'));
		if(k) D.s[k][i]++;
		//cout<<k<<endl;
		}
		//cout<<tem<<endl;
	}
}
void work()
{
	str[0]="\0";
	update();
	int ans=qmi(L);
	G=G*quickpow(D,L);
	ans-=G.s[1][1];
	ans=(ans+mod)%mod;
	printf("%d",ans);
}
int main()
{
	freopen("textgen.in","r",stdin);
	freopen("textgen.out","w",stdout);
	scanf("%d%d",&N,&L);
	for(int i=1;i<=N;i++)
		cin>>str[i];
	work();
	return 0;
}