题目大意：
从字典中选择N个单词，然后确定开始单词S,结束单词T。
A，B两个人轮流选择单词，在K次内，先手A从开始单词S出发回到结束单词T的次数。
用单词作为状态转换，用map映射。
当a单词的最后一个字母与b单词的最前一个字母相同时，则a状态可以转化至b状态matrix[a][b]=1;
接下来要处理的就是K次内这个问题了。我们可以很简单的得到如下的
M+M^3+M^5+M^7+M^9.....
因为先手嘛... 每次的奇数步都会由自己掌控。
这个等比矩阵和怎么求呢？？
我们知道一种矩阵构造法：
这个矩阵的N次方的右上角小矩阵就是A^0+...+A^(N-1)了。
其实呢，这种构造方法更好，直接N次方右上角小矩阵就是A+A^2+....+A^N了...
嘿嘿~
那么回到正题：
我们要求A+A^3+A^5....这种奇数项矩阵的和怎么办呢？
也可以构造矩阵：
大家自己乘一下就会发现规律的....
只是这种方法不是很好罢了....
代码也很丑...
#include<iostream>
#include<string>
#include<cstdio>
#include<map>
using namespace std;int temp[66][66],res[66][66],temp2[66][66];
int n,k;
int s,t;
void xmult( int a[][66],int b[][66],int n )
{int c[66][66];memset( c,0,sizeof(c) );for( int i=0;i<n;i++ )for( int k=0;k<n;k++ )if( a[i][k] )for( int j=0;j<n;j++ )c[i][j]+=a[i][k]*b[k][j];for( int i=0;i<n;i++ )for( int j=0;j<n;j++ )a[i][j]=c[i][j]%10001;
}void mpower( int m[][66],int k,int n )
{if( k<=1 ){for( int i=0;i<n;i++ )for( int j=0;j<n;j++ )m[i][j]=temp2[i][j]%10001;return ;}mpower( m,k>>1,n );xmult( m,m,n );if( k&1 )xmult( m,temp2,n );
}void init()
{ map<string,int>map;string str[44];cin>>n;for( int i=0;i<n;i++ ){ cin>>str[i];map[str[i]]=i;}string src,dst;memset( temp,0,sizeof(temp) );cin>>src>>dst>>k;s=map[src],t=map[dst];for( int i=0;i<n;i++ ){ int len=str[i].length();for( int j=0;j<n;j++ )if( str[j][0]==str[i][len-1] )temp[map[str[i]]][map[str[j]]]++;}memset( temp2,0,sizeof(temp2) );for( int i=0;i<n;i++ )temp2[i][i]=1;xmult(temp2,temp,n);xmult(temp2,temp,n);for( int i=0;i<n;i++ ){ temp2[i+n][i+n]=1;temp[i+n][i+n]=1;for( int j=0;j<n;j++ ){ temp2[i][j+n]=temp2[i][j];temp[i][j+n]=temp[i][j];}}memset( res,0,sizeof(res) );
} int main()
{int T;cin>>T;while( T-- ){init();if( (k-1)/2 ){mpower(res,(k-1)/2,2*n);xmult(temp,res,2*n);}printf( "%d\n",temp[s][t+n]%10001 );}return 0;
}