学步园

题目链接:    http://poj.org/problem?id=3233

题目大意:    给出矩阵n*n的矩阵A，求对m取模后的结果

解题思路:    k的非常大，直接求解时间复杂度太高

                   定义F[k]=A+A^2+A^3+....A^k                                               

                   利用乘法的分配律可以减少运算 F[6]=A+A^2+A^3+A^4+A^5+A^6=(A+A^2+A^3)+(A+A^2+A^3)*A^3                     

                   每次运算二分减少规模，二分之后再二分

                   奇数: F[n]=F[n-1]+A^n         

                   偶数: F[n]=F[n/2]+F[n/2]*A^n/2

                         两处地方用到了二分：二分缩小总的规模，二进制思想的矩阵快速幂

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 31
int n,m,k;
typedef struct snode{
	int edge[MAX][MAX];
}Matrix;
Matrix map,ant,h,hh,c,d;

void mult(Matrix &a,Matrix &b,Matrix &c)   //矩阵C=A*B
{
	int i,j,k2;
	memset(h.edge,0,sizeof(h.edge));
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			for(k2=0;k2<n;k2++)
			{
				h.edge[i][j]+=(a.edge[i][k2]*b.edge[k2][j]);  //**分开写，否则会WA
				h.edge[i][j]%=m;                              //**
			}
	for(i=0;i<n;i++)           //赋值
		for(j=0;j<n;j++)
			c.edge[i][j]=h.edge[i][j];
}

Matrix KSM(Matrix a,int k)     //快速幂求矩阵A^k
{
	int i;
	memset(hh.edge,0,sizeof(hh.edge));
	for(i=0;i<n;i++)
		hh.edge[i][i]=1;
	while(k>=1)
	{
		if(k&1)
			mult(a,hh,hh);
		mult(a,a,a);
		k>>=1;
	}
	return hh;
}

Matrix Sum(Matrix a,Matrix b)   //A,B矩阵相加
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
            h.edge[i][j]=(a.edge[i][j]+b.edge[i][j]);
            h.edge[i][j]%=m;
        }
	return h;
}

Matrix F(int x)
{
	if(x<=1)
		return map;
	else if(x%2)  //n为奇数:F[n]=F[n/2]+F[n/2]*A^(n/2)
	{
		c=F(x-1);
		d=KSM(map,x);
		return Sum(c,d);
	}
	else          //n为偶数:F[n]=F[n-1]+A^n
	{
		c=F(x/2);
		d=KSM(map,x/2);   //二分减少规模
		mult(c,d,d);
		return Sum(c,d);
	}
}

int main()
{
	int i,j;
	scanf("%d%d%d",&n,&k,&m);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&map.edge[i][j]);
	ant=F(k);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%d",ant.edge[i][j]);
			if(j!=n-1)                //每行最后的空格去掉，防PE
				printf(" ");
		}
		printf("\n");
	}
	return 0;
}