链接：http://acm.hdu.edu.cn/showproblem.php?pid=5318

The Goddess Of The Moon

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 438    Accepted Submission(s): 150

2

10 50

12 1213 1212 1313231 12312413 12312 4123 1231 3 131

5 50

121 123 213 132 321

86814837

797922656

Hint

11 111 is different with 111 11

题意：有n个小楼梯，假设两个楼梯的 前缀等于还有一个的后缀就能够首尾相连，前缀后缀长度要大于等于2。

问m个楼梯组成。有多少种组成方法。

做法：要去重，然后judge  每一个楼梯能不能连，构造出构造矩阵。初始矩阵第一行全为1，然后矩阵高速幂。

#include <cstdio>

#include <algorithm>

#include <stdio.h>

#include <string>

#include <set>

#include <math.h>

#include <string.h>

#include <iostream>

using namespace std;

#define Matr 55 //矩阵大小,注意能小就小   矩阵从1開始   所以Matr 要+1   最大能够100

#define ll __int64

struct mat//矩阵结构体。a表示内容，size大小 矩阵从1開始   但size不用加一

{

    ll a[Matr][Matr];

    mat()//构造函数

    {

        memset(a,0,sizeof(a));

    }

};

int Size=  0 ;

ll mod= 1000000007;

mat multi(mat m1,mat m2)//两个相等矩阵的乘法，对于稀疏矩阵。有0处不用运算的优化

{

    mat ans=mat();

    for(int i=1;i<=Size;i++)

        for(int j=1;j<=Size;j++)

            if(m1.a[i][j])//稀疏矩阵优化

                for(int k=1;k<=Size;k++)

                    ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k])%mod; //i行k列第j项

    return ans;

}

mat quickmulti(mat m,ll n)//二分高速幂

{

    mat ans=mat();

    int i;

    for(i=1;i<=Size;i++)ans.a[i][i]=1;

    while(n)

    {

        if(n&1)ans=multi(m,ans);//奇乘偶子乘 挺好记的.

        m=multi(m,m);

        n>>=1;

    }

    return ans;

}

void print(mat m)//输出矩阵信息，debug用

{

    int i,j;

    printf("%d\n",Size);

    for(i=1;i<=Size;i++)

    {

        for(j=1;j<=Size;j++)

			printf("%d ",m.a[i][j]);

        printf("\n");

    }

}

set<string> my;

string str[60];

int judge(string a,string b)

{

	for(int i=2;i<=a.size()&&i<=b.size();i++)

	{

		int flag=1;

		for(int j=0;j<i;j++)

		{

			if(a[a.size()-i+j]!=b[j])

				flag=0;

		}

		if(flag)

			return 1;

	}

	return 0;

}

int  main()

{

	int t;

	scanf("%d",&t);

	while(t--)

	{

		int n,m;

		scanf("%d%d",&n,&m);

		int kk=0;

		my.clear();

		for(int i=0;i<n;i++)

		{

			string ss;

			cin>>ss;

			if(my.find(ss)==my.end())

			{

				my.insert(ss);

				str[++kk]=ss;

			}

		}

		n=kk;

		if(m==0||n==0)

		{

			printf("0\n");

			continue;

		}

		mat gouzao=mat(),chu=mat();//构造矩阵  初始矩阵  

		for(int i=1;i<=kk;i++)

		{

			for(int j=1;j<=kk;j++)

			{

				if(judge(str[i],str[j]))

				gouzao.a[i][j]=1;

			}

		}

		for(int i=1;i<=kk;i++)

		{

			chu.a[1][i]=1;

		}

		Size=kk;

		chu=multi(chu,quickmulti(gouzao,m-1));

		__int64 ans=0;

		for(int i=1;i<=kk;i++)

		{

			ans=(ans+chu.a[1][i])%mod;

		}

		printf("%I64d\n",ans);

	}

	return 0;

}