The Goddess Of The Moon

【题意】给出n(<=50)个串，任意拼接m(<=10^9)个串有多少种可能方案，a和b字符串可拼接必须满足a的某个长度>=2的后缀是b的前缀，那么a可以拼在b前面。

【分析】m巨大，必须使用快速幂，其实是《十个利用矩阵乘法解决的经典题目(Maxtrix67)》一文中经典题目8。

经典题目8 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

然后把这题转换为一个有向图矩阵，(i,j)可以拼接就是1，否则0，跑一下快速矩阵幂即可。注意有重复串。

【AC CODE】1435ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <bitset>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50+10;
const LL MOD = 1000000007;
int a[MAXN],n;
struct MATRIX{//矩阵
	LL num[MAXN][MAXN];
};
set<int> vis;

MATRIX mul(const MATRIX& a, const MATRIX& b)//矩阵a*b
{
	MATRIX ans;
	clc(ans.num,0);
	rep(i,0,n)
	{
		rep(j,0,n)
		{
			rep(k,0,n)
				ans.num[i][j] = (ans.num[i][j]+(a.num[i][k]*b.num[k][j]%MOD+MOD)%MOD)%MOD;
		}
	}
	return ans;
}
MATRIX pow_mod(MATRIX x, int cnt)//快速幂
{
	MATRIX ans;
	clc(ans.num,0);
	rep(i,0,n) ans.num[i][i] = 1;
	while(cnt)
	{
		if(cnt&1) ans = mul(ans,x);
		x = mul(x,x);
		cnt >>= 1;
	}
	return ans;
}
bool ok(int x, int y)
{
	char aa[MAXN],bb[MAXN];
	sprintf(aa,"%d",x);sprintf(bb,"%d",y);
	int len1 = strlen(aa), len2 = strlen(bb);
	per(i,len1-2,0)
	{
		char *p;
		if((p = strstr(bb,aa+i)) && p == bb) return true;
	}
	return false;
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int m,cnt = 0;
		scanf("%d %d", &n, &m);
		vis.clear();
		rep(i,0,n)
		{
			int tmp;
			scanf("%d", &tmp);
			if(vis.find(tmp) == vis.end())
			{
				a[cnt++] = tmp;
				vis.insert(tmp);
			}
		}
		n = cnt;
		if(0 == m)
		{
			puts("0");
			continue;
		}
		MATRIX x;
		rep(i,0,n)
		{
			rep(j,0,n)
			{
				x.num[i][j] = ok(a[i],a[j]);
			}
		}
		MATRIX ans = pow_mod(x,m-1);
		LL sum = 0;
		rep(i,0,n) rep(j,0,n) sum = (sum+ans.num[i][j])%MOD;
		printf("%I64d\n", sum);
	}
	return 0;
}