Matrix Power Series
Description
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
题目大意:给出一个一个n*n的矩阵、k和m,求S(上面有,复制粘贴格式错误,QAQ)(每个元素对m取模)
思路:
(第一次做根本就没有思路好吧,想了半天没搞懂,搜了搜博客,看到这张图秒懂QAQ)
来自https://www.cnblogs.com/sj-gank/p/11771343.html
E是单位矩阵;
看完应该都是秒懂的吧QAQ
虽然实现还是花了很久,各种找bug。
AC代码:
#include<iostream> #include<cstring> using namespace std; #define ll long long const int maxn=30; int mod=10000; ll T,n,k; struct matrix{ ll a[maxn][maxn]; matrix(){ memset(a,0,sizeof(a)); } }; struct Matrix{ matrix b[2][2]; Matrix(){ memset(b,0,sizeof(b)); } }; matrix mul(matrix a,matrix b){ matrix res; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j])%mod; return res; } matrix add(matrix a,matrix b){ matrix res; for(int i=0;i<n;i++) for(int j=0;j<n;j++) res.a[i][j] = (a.a[i][j] + b.a[i][j])%mod; return res; } Matrix mul(Matrix a,Matrix b){ Matrix res; for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) res.b[i][j] = add(res.b[i][j] , mul(a.b[i][k] , b.b[k][j])); return res; } matrix qpow(matrix A,ll m){//方阵A的m次幂 matrix ans; for(int i=0;i<n;i++) ans.a[i][i]=1; //单位矩阵 while(m){ if(m&1)ans=mul(ans,A); A=mul(A,A); m>>=1; } return ans; } Matrix qpow(Matrix A,ll m){ Matrix ans; for(int i=0;i<2;i++) for(int j=0;j<n;j++) ans.b[i][i].a[j][j]=1; //单位矩阵 while(m){ if(m&1)ans=mul(ans,A); A=mul(A,A); m>>=1; } return ans; } Matrix M; int main() { cin>>n>>k>>mod; matrix A; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>M.b[0][0].a[i][j]; for(int i=0;i<n;i++){ M.b[0][1].a[i][i]=1; M.b[1][1].a[i][i]=1; } Matrix res=qpow(M,k+1); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j){ if(res.b[0][1].a[i][j]==0) cout<<mod-1<<' '; else cout<<res.b[0][1].a[i][j]-1<<' '; }else cout<<res.b[0][1].a[i][j]<<' '; } cout<<endl; } }