首页 > 代码库 > nyoj_299_Matrix Power Series_矩阵快速幂
nyoj_299_Matrix Power Series_矩阵快速幂
Matrix Power Series
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
- Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.
- 输入
- The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10^9) and m (m < 10^4). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.
- 输出
- Output the elements of S modulo m in the same way as A is given.
- 样例输入
2 2 40 11 1
- 样例输出
1 22 3
- 来源
- POJ Monthly
- 上传者
- 张云聪
#include <iostream>#include <cstdio>using namespace std;int M=1000007;struct Matrix{ long int line,column; long int m[40][40];};struct Matr{ long int line,column; long int m[70][70]; Matr(Matrix x){ line =x.line*2; column=x.column*2; for(int i=0;i<x.line*2;i++){ for(int j=0;j<x.column;j++){ m[i][j]=x.m[i%x.line][j]; } } for(int i=0;i<x.line;i++){ for(int j=x.column;j<x.column*2;j++){ m[i][j]=0; } } for(int i=x.line;i<x.line*2;i++){ for(int j=x.column;j<x.column*2;j++){ if(i==j){ m[i][j]=1; }else{ m[i][j]=0; } } } }};Matr mult(Matr a,Matr b){ Matr ans(a); ans.line=a.line; ans.column=b.column; //ans=inist(ans,0); for(int i=0;i<ans.line;i++){ for(int j=0;j<ans.column;j++){ ans.m[i][j]=0; for(int k=0;k<ans.column;k++){ ans.m[i][j]+=(a.m[i][k]*b.m[k][j]); ans.m[i][j]%=M; } } } return ans;}Matr fast_matrix(Matr x,int n){ Matr an(x),tmp(x); for(int i=0;i<x.line;i++){ for(int j=0;j<x.column;j++){ an.m[i][j]=x.m[i+x.line/2][j]; } } an.line/=2; while(n){ if(n%2!=0){ an=mult(an,tmp); } tmp=mult(tmp,tmp); n>>=1; } return an;}int main(){ int n,m,k; Matrix a; scanf("%d %d %d",&n,&k,&m); M=m; a.line=n; a.column=n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&a.m[i][j]); } } Matr ans(a); Matr ans2=fast_matrix(ans,k-1); for(int i=0;i<ans2.line;i++){ for(int j=0;j<ans2.column/2;j++){ printf("%d ",ans2.m[i][j]); } printf("\n"); } return 0;}
nyoj_299_Matrix Power Series_矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。