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 4 0 1 1 1 Sample Output 1 2 2 3
等比矩阵这玩意… a1 01 n次方以后… a^n 1+…+a^n-1 0 1
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int n,k,mo; struct p { int q[65][65]; }; p cheng(p q,p w,int t) { p fs; memset(fs.q,0,sizeof(fs.q)); for(int a=1;a<=t;a++) { for(int b=1;b<=t;b++) { for(int c=1;c<=t;c++) { fs.q[a][b]+=q.q[a][c]*w.q[c][b]%mo; fs.q[a][b]%=mo; } } } return fs; } p ksm(p ds,int zs,int t) { p fs; for(int a=1;a<=t;a++) { for(int b=1;b<=t;b++) { if(a==b)fs.q[a][b]=1; else fs.q[a][b]=0; } } while(zs) { if(zs&1)fs=cheng(fs,ds,t); ds=cheng(ds,ds,t); zs>>=1; } return fs; } p ys; int main() { cin>>n>>k>>mo; for(int a=1;a<=n;a++) { for(int b=1;b<=n;b++) { scanf("%d",&ys.q[a][b]); if(a==b)ys.q[a][b+n]=ys.q[a+n][b+n]=1; } } ys=ksm(ys,k+1,2*n); for(int a=1;a<=n;a++) { for(int b=1;b<=n;b++) { if(a!=b)continue; ys.q[a][b+n]--; if(ys.q[a][b+n]>=0)continue; ys.q[a][b+n]+=mo; } } for(int a=1;a<=n;a++) { for(int b=1;b<=n;b++) { cout<<ys.q[a][b+n]; if(b<n)cout<<" "; } cout<<endl; } }