The Goddess Of The Moon
Sample Input
2
10 50
12 1213 1212 1313231 12312413 12312 4123 1231 3 131
5 50
121 123 213 132 321
10 50
12 1213 1212 1313231 12312413 12312 4123 1231 3 131
5 50
121 123 213 132 321
Sample Output
86814837
797922656
797922656
题意：给你n个字符串，若是一个的后缀与一个的前缀相同的大于1，则表示这两个可以连接到一起，问M个字符串相连的方案数
若a b可以合并，可以让他们相连，然后求在一个图中走m-1步的方案数，
两点之间所走的步数为m-1的不同走法有多少种——矩阵快速幂的经典问题
因为求不同方案--->去重
（在别人博客看到的，表示以前并不知道这个，既然有点像模板题，写写学习下）
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> using namespace std; const int maxn = 55;
const int mod = 1e9+7; int n, m, a[maxn]; struct Mat
{
int s[maxn][maxn];
Mat ()
{
memset(s, 0, sizeof(s));
}
Mat operator * (const Mat& b)
{
Mat ret;
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
ret.s[i][j] = (ret.s[i][j] + 1LL * s[i][k] * b.s[k][j] % mod) % mod;
}
}
return ret;
}
}; bool work(int a,int b)
{
char p[15], q[15];
sprintf(p, "%d", a);
sprintf(q, "%d", b); int l1 = strlen(p);
int l2 = strlen(q);
for(int i = 0; i < l1; i++)
{
int k = 0;
while(i + k < l1 && k < l2 && p[i+k] == q[k])
{
k++;
}
if(i + k == l1 && k > 1)
return true;
}
return false;
} Mat solve()
{
Mat lp;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
if(work(a[i],a[j]))
lp.s[i][j] = 1;
}
return lp;
} Mat pow_mat(Mat x, int z)
{
Mat ret;
for (int i = 0; i < n; i++)
ret.s[i][i] = 1;
while (z)
{
if (z&1)
ret = ret * x;
x = x * x;
z >>= 1;
}
return ret;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m); for(int i = 0; i <n; i++)
scanf("%d",&a[i]);
sort(a,a+n);
n = unique(a,a+n) - a; if (n == 0 || m == 0)
{
printf("0\n");
continue;
}
Mat tp = solve();
Mat tmp = pow_mat(tp,m-1); long long ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
ans = (long long)(ans + tmp.s[i][j])%mod;
printf("%I64d\n",ans);
}
} 主要部分： struct Matrix {
LL m[55][55];
};
Matrix init; Matrix MatrixMul(Matrix a, Matrix b){
Matrix c;
int i,j,k;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
c.m[i][j]=0;
for(k=0;k<N;k++){
c.m[i][j]+=(a.m[i][k]*b.m[k][j]);
c.m[i][j]%=kmod;
}
}
}
return c;
} Matrix QuickPow(Matrix m,int p){
Matrix b;
int i;
memset(b.m,0,sizeof b.m);
for(i=0;i<N;i++)
b.m[i][i]=1;
while(p){
if(p%2) b=MatrixMul(b,m);
p/=2;
m=MatrixMul(m,m);
}
return b;
}