首页 > 其他 > 详细

poj3233(Matrix Power Series)解题报告

时间:2017-11-18 00:44:54      阅读:315      评论:0      收藏:0      [点我收藏+]

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

感觉做起来包含了矩阵的所有运算了,矩阵加法,矩阵乘法,矩阵快速幂,啊。。。写了好久

题解 : k最大10^9,太大了,但经过观察可以折半计算,即 :

   当k是偶数,f[k] = f[k/2] * ( 1 + A^(k/2) )
    k是奇数,f[k] = f[k-1] + A^(k)

AC代码加注释:

 

#include<stdio.h>
#include<algorithm>
#include<string.h> 
using namespace std;

int A[32][32],N,m,sum[32][32]={0};

void N_matrix(int (*p)[32],int (*a)[32],int (*b)[32],int N) //矩阵p=矩阵a*矩阵b 
{	int temp[32][32];
	int i,j,k;
	memset(temp,0,sizeof(temp));
	
	for(i=0;i<N;i++)
	for(j=0;j<N;j++)
	for(k=0;k<N;k++)
	temp[i][j]+=a[i][k]*b[k][j]%m;
	
	for(i=0;i<N;i++)
	for(j=0;j<N;j++)
	p[i][j]=temp[i][j]%m;
}
void N_matrixadd(int (*p)[32],int a[32][32],int b[32][32],int N) //矩阵p=矩阵a+矩阵b
{	
	
	for(int i=0;i<N;i++)
	for(int j=0;j<N;j++)
	p[i][j]=(a[i][j]+b[i][j])%m;
}
void matrix_pow(int (*A)[32],int (*p)[32],int n,int N) //矩阵快速幂 ,n次方 
{	int temp[32][32]={0},i=0,j=0;
	
	while(i<N)		//置为E矩阵 
	{	temp[i][j]=1;
		i++,j++; 
		
	}
	for(i=0;i<N;i++)
	for(j=0;j<N;j++)
	p[i][j]=A[i][j];
	
	for(;n;n/=2)
	{	if(n&1)
		{	N_matrix(temp,temp,p,N);
			
		}
		N_matrix(p,p,p,N);
	}
		for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		p[i][j]=temp[i][j];  //将最终结果赋给p 
}

void digui(int k)
{	int temp[32][32]={0};
	
	int y[32][32]={0};
	if(k==1)
	{	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		sum[i][j]=A[i][j];
		return;
	}
			if(k&1)
			{	
				matrix_pow(A,y,k,N);
				k--;
			}
		digui(k/2);
		
		N_matrixadd(temp,temp,sum,N);
		
		int x[32][32];
		matrix_pow(A,x,k/2,N);

		N_matrix(x,temp,x,N);
		
		N_matrixadd(temp,temp,x,N);
		
		N_matrixadd(temp,temp,y,N);
		
		for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		sum[i][j]=temp[i][j];  //记录每一层递归最终结果 
}

int main()
{	int k;
	scanf("%d%d%d",&N,&k,&m);
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		scanf("%d",&A[i][j]);
	digui(k);
	
	for(int i=0;i<N;i++)
		{ 	printf("%d",sum[i][0]%m);
			for(int j=1;j<N;j++)
		 	printf(" %d",sum[i][j]%m);
		
			printf("\n");
		}
	return 0;
}

 

  

 

poj3233(Matrix Power Series)解题报告

原文:http://www.cnblogs.com/lnu161403214/p/7854139.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!