首页 > 代码库 > 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_矩阵快速幂