2014
02-12

# Word Game

If you have a circle consists of L characters. We can define one of them as 0th character, and then 1st, 2nd …… (L -1)th along the clockwise. A string beginning with the ith character can be get from this circle, let’s call it p[i] (All of these string has a length of L). From 0 to L -1, if there exists exactly K positions i make p[i] as same as p[0], then we call it a magic word.
Give you n strings and a K. Please use all of these strings to creat a new string p. Tell me how many ways exists to construct a string p and make it a magic word.

The input contains several cases. Each case starts with two integer n and K. Then follows n lines, each line contain a string. 0 < n <= 8, 0 < K <= 200, each string contain between 1 and 20 characters. Input ends with a case n = 0 and K = 0.

The input contains several cases. Each case starts with two integer n and K. Then follows n lines, each line contain a string. 0 < n <= 8, 0 < K <= 200, each string contain between 1 and 20 characters. Input ends with a case n = 0 and K = 0.

3 3
AAB
AAB
AAB
0 0

6

Hinthints:
Use these strings, you can construct six "AABAABAAB". 

#include <iostream>
#include <string>
#include<cmath>
using namespace std;
#define MAXN 35
#define MOD 10001

struct mat
{
int n,m;
int data[MAXN][MAXN];
}A;
int n;

int mul(mat& c,const mat& a,const mat& b)
{
int i,j,k;
if (a.m!=b.n)
return 0;
c.n=a.n,c.m=b.m;
for (i=0;i<c.n;i++)
for (j=0;j<c.m;j++)
for (c.data[i][j]=k=0;k<a.m;k++)
{
c.data[i][j]+=a.data[i][k]*b.data[k][j];
c.data[i][j]%=MOD;
}
return 1;
}

bool fit(char s1[],char s2[])
{
if(s1[strlen(s1)-1]==s2[0])
return true;
return false;
}
int sum=0;

mat powmat(mat a,int k)
{
int i,j;
mat res,tt=a,t1,t2;
if(k==1)
{
return a;
}
tt=powmat(a,k/2);
t1=tt;
mul(tt,t1,t1);
if(k&1)
mul(res,a,tt);
else
res=tt;
return res;
}

mat plusmat(mat & a,int k)//cal A1+A2+A3+...Ak
{
int i,j;
mat res,tt;
if(k==1)
return a;
else
{
mat temp=powmat(a,k/2),pow2t;
if(k%2)
{
pow2t=powmat(temp,2);
mul(tt,pow2t,a);
pow2t=tt;
}
for(i=0;i<n;i++)
temp.data[i][i]++;
mul(res,temp,plusmat(a,k/2));
if(k%2)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
res.data[i][j]+=pow2t.data[i][j];
return res;
}
}
int main()
{
char str[MAXN][15];
int T,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
A.m=A.n=n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
A.data[i][j]=0;
for(i=0;i<n;i++)
scanf("%s",str[i]);
//connect edge
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(fit(str[i],str[j]))
A.data[i][j]=1;
}
scanf("%s",str[i]);
for(j=0;j<n;j++)
if(strcmp(str[i],str[j])==0)
break;
int start=j;
scanf("%s",str[++i]);
for(j=0;j<n;j++)
if(strcmp(str[i],str[j])==0)
break;
int end=j;
int times;
scanf("%d",×);
//multiple matrix
mat ww=A,res;
mat pow2;
mul(pow2,A,A);
times--;
if(times/2>0)
{
res=plusmat(pow2,times/2);
mul(ww,A,res);
printf("%d/n",ww.data[start][end]+A.data[start][end]);
}
else
printf("%d/n",A.data[start][end]);
}
}

1. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

2. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了