首页 > ACM题库 > HDU-杭电 > hdu 2657 Word Game-快速幂-[解题报告]C++
2014
02-12

hdu 2657 Word Game-快速幂-[解题报告]C++

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

Hint
hints: 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]);
	}
}

解题转自:http://blog.csdn.net/abcjennifer/article/details/5892419


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

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