首页 > 代码库 > POJ3233 Matrix Power Series

POJ3233 Matrix Power Series

2024-09-21 16:05:58   216人阅读

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). 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^1+A^2+A^3+A^4)*(A^4 + I) = A^1+A^2+A^3+A^4+A^5+A^6+A^7+A^7

项数为奇数的时候要加上那个奇数项

 

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 int read(){ 8     int x=0,f=1;char ch=getchar(); 9     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}10     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}11     return x*f;12 }13 int n,m,K;14 struct Mat{15     int x[32][32];16     void init(){17         memset(x,0,sizeof x);18         for(int i=1;i<=n;i++)x[i][i]=1;19         return;20     }21     Mat operator + (const Mat &b){22         Mat res;23         for(int i=1;i<=n;i++)24             for(int j=1;j<=n;j++)25                 res.x[i][j]=(x[i][j]+b.x[i][j])%m;26         return res;27     }28     Mat operator * (const Mat &b){29         Mat res;30         for(int i=1;i<=n;i++)31             for(int j=1;j<=n;j++){32                 res.x[i][j]=0;33                 for(int k=1;k<=n;k++)34                     (res.x[i][j]+=x[i][k]*b.x[k][j]%m)%=m;35             }36         return res;37     }38 }I,A;39 inline Mat ksm(Mat a,int k){40     Mat res;res.init();41     while(k){42         if(k&1)res=res*a;43         a=a*a;44         k>>=1;45     }46     return res;47 }48 Mat Bcalc(int k){49     if(k==1)return A;50     if(k&1)51         return (ksm(A,k>>1)+I)*Bcalc(k>>1)+ksm(A,k);52     return (ksm(A,k>>1)+I)*Bcalc(k>>1);53 }54 int main(){55     int i,j;56     n=read();K=read();m=read();57     I.init();58     for(i=1;i<=n;i++)59         for(j=1;j<=n;j++)60             A.x[i][j]=read();61     Mat ans=Bcalc(K);62     for(i=1;i<=n;i++){63         for(j=1;j<=n;j++)64             printf("%d ",ans.x[i][j]);65         printf("\n");66     }67     return 0;68 }

 

POJ3233 Matrix Power Series


联系
我们