链接: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
Each of the test case begins with two integers n, m.
(n <= 50, m <= 1e9)
The following line contains n integer numbers describe the n kinds of chains.
All the Integers are less or equal than 1e9.
题意:有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;
}