C++14(g++5.4) 解法, 执行用时: 1000ms, 内存消耗: 1588K, 提交时间: 2020-08-05 20:28:35

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod=1e9+7;
int n,x,t,dp[30][30]; 
struct mat{
	int a[200][200];
}m,u;
char s[30][30];
mat matmul(mat c,mat d){
	int h=n*6;
	mat tmp;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=h;j++){
			tmp.a[i][j]=0;
			for(int k=1;k<=h;k++)
				tmp.a[i][j]=(tmp.a[i][j]+1LL*c.a[i][k]*d.a[k][j]%mod)%mod;
		}
	return tmp;		
}
void matpow(int b){
	for(int i=1;i<=6*n;i++)u.a[i][i]=1;
	while(b){
		if(b&1)u=matmul(u,m);
		m=matmul(m,m);
		b>>=1;
	}
	printf("%d",u.a[1][2]);
}
int solve(int a,int b){
	memset(dp,0,sizeof(dp));
	int ans=0;
	int lena=strlen(s[a]+1),lenb=strlen(s[b]+1);
	for(int i=1;i<=lena;i++)
		for(int j=1;j<=lenb;j++)
			if(s[a][i]==s[b][j])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
	for(int i=1;i<=lena;i++)
		for(int j=1;j<=lenb;j++)
			ans=max(ans,dp[i][j]);
	return ans+1;
}
int main(){
	scanf("%d%d",&n,&t);n+=2;
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=5;j++)m.a[i+j*n][i+n*(j-1)]=1;
		if(i==2)continue;
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			x=solve(i,j);
		//	cout<<i<<" "<<j<<" "<<x<<"\n";
			m.a[i][j+n*(x-1)]=1;
		}
	}
	matpow(t);
	return 0;
}