poj 3233 Matrix Power Series-白红宇

poj 3233 Matrix Power Series

阅读量：2439 次

发布时间：2019-05-10

本文共 1721 字，大约阅读时间需要 5 分钟。

Matrix Power Series

Time Limit: 3000MS		Memory Limit: 131072K
Total Submissions: 15997		Accepted: 6840

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 40 11 1

Sample Output

1 22 3

题意：给出矩阵A，求S = A + A^2 + A^3 + … + A^k ；

解题思路：二分+快速矩阵幂

在这里所谓的二分的意思是：举例说明假设k=18，则

S=A+A^2+A^3+A^4+A^5+A^6+A^7+A^8+A^9+A^10+A^11+A^12+A^13+A^14+A^15+A^16+A^17+A^18

S=(A+A^2+A^3+A^4+A^5+A^6+A^7+A^8+A^9)*(1+A^9)

S=(A+A^2+A^3+A^4)*(1+A^4)*(1+A^9)

S=(A+A^2)*(1+A^2)*(1+A^4)*(1+A^9)

S=A*(1+A)*(1+A^2)*(1+A^4)*(1+A^9)

参考代码如下：

#include 
   
    #include 
    
     using namespace std;int n,m,k;struct Matrix{	int mat[31][31];};Matrix add(Matrix a,Matrix b){	Matrix ans;	for (int i=0;i
     
      =m){				ans.mat[i][j]%=m;			}		}	}	return ans;}Matrix mul(Matrix a,Matrix b){	Matrix ans;	for (int i=0;i
      
       =m){					ans.mat[i][j]%=m;				}			}		}	}	return ans;}Matrix Init(){	Matrix ans;	for (int i=0;i
       
        >=1;	}	return ans;}Matrix Calculate(Matrix a,int k){	Matrix ans;	memset(ans.mat,0,sizeof(ans.mat));	Matrix temp=Init();	if (k==1)		return a;	if (k%2)		ans=add(Calculate(a,k-1),exp(a,k));	else{		Matrix s=Calculate(a,k/2);		ans=add(s,mul(s,exp(a,k/2)));	}	return ans;}int main(){	Matrix a;	while (cin>>n>>k>>m){		for (int i=0;i
        
         >a.mat[i][j]; if (a.mat[i][j]>=m){ a.mat[i][j]%=m; } } } Matrix ans=Calculate(a,k); for (int i=0;i

转载地址：http://ufbqb.baihongyu.com/

你可能感兴趣的文章