记录编号	577978	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1676]文本生成器	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2023-01-03 20:39:38	内存使用	1.40 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define fi first
#define se second
#define pb push_back
const int mod=10007;
const int N=10+5;
const int M=6+4;
int n,m,S;
int sl[N],suml[N]={0};
char s[N][M],t[M];
int gid(int x,int y){
	if (!x)return 0;
	return suml[x-1]+y;
}
bool chck(int x,int y,int len){
	for (int i=1;i<=y;i++){
		if (t[len-y+i]!=s[x][i])return 0;
	}
	return 1;
}
int maxsuf(int len){
	int mx=0,mxid=0,num=0;
	for (int x=1;x<=n;x++){
		for (int y=1;y<=min(sl[x],len);y++){
			if (chck(x,y,len)){
				if (y==sl[x])return -1;
				if (y>mx){
					mx=y;mxid=gid(x,y);
				}
			}
		}
	}
	return mxid;
} 
struct sdf{
	int p[65][65];
	sdf(){
		for (int i=0;i<=S;i++){
			for (int j=0;j<=S;j++)p[i][j]=0;
		}
	}
	sdf operator*(const sdf&x)const{
		sdf tmp;
		for (int i=0;i<=S;i++){
			for (int j=0;j<=S;j++){
				for (int k=0;k<=S;k++){
					tmp.p[i][j]=(tmp.p[i][j]+p[i][k]*x.p[k][j]%mod)%mod;
				}
			}
		}
		return tmp;
	}
}A,B,C,id;
sdf fst(sdf x,int y){
	if (!y)return id;
	if (y&1)return x*fst(x,y-1);
	C=fst(x,y/2);return C*C;
}
int qpow(int x,int y){
	if (!y)return 1;
	if (y&1)return x*qpow(x,y-1)%mod;
	int p=qpow(x,y/2);return p*p%mod;
}
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",s[i]+1);
		sl[i]=strlen(s[i]+1);
		suml[i]=suml[i-1]+sl[i];
	}
	S=suml[n];
	for (int i=0;i<=S;i++)id.p[i][i]=1;
	for (char k='A',len=1;k<='Z';k++){
		t[len]=k;
		int mxid=maxsuf(len);
		if (mxid==-1)continue;
		A.p[0][mxid]++;
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=sl[i];j++){
			int len=j+1,id=gid(i,j);
			for (int k=1;k<=j;k++)t[k]=s[i][k];
			for (char k='A';k<='Z';k++){
				t[len]=k;
				int mxid=maxsuf(len);
				if (mxid==-1)continue;
				A.p[id][mxid]++;
			}
		}
	}
	B=fst(A,m);
	int ans=0,tot=qpow(26,m);
	for (int i=0;i<=S;i++)ans=(ans+B.p[0][i])%mod;
	printf("%d\n",((tot-ans)%mod+mod)%mod);
	return 0;
}