求矩阵的 k 次幂
#include <iostream> #include <cmath> #include <algorithm> using namespace std; #define N 100 const int mod =1e9+7; #define int long long struct matrix { int a[N+2][N+2]; }; matrix m1; int n; void init_(matrix &x){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { x.a[i][j]=0; if(i==j) x.a[i][j]=1; } } matrix mul(matrix &x,matrix &y){ int i,j,k; matrix z; for(i=1;i<=n;i++) for(j=1;j<=n;j++){ z.a[i][j]=0; for(k=1;k<=n;k++) z.a[i][j]+=x.a[i][k]*y.a[k][j], z.a[i][j]%=mod; } return z; } matrix ksm(matrix &x,int k){ matrix tmp=x, ans; init_(ans); while(k){ if(k&1) ans=mul(ans,tmp); tmp=mul(tmp,tmp); k/=2; } return ans; } signed main(){ std::ios::sync_with_stdio(0); int m; cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)cin>>m1.a[i][j]; matrix t= ksm(m1,m); for(int i=1;i<=n;cout<<endl,i++) for(int j=1;j<=n;j++) cout<<t.a[i][j]%mod<<' '; }
标签:matrix,int,矩阵,long,m1,include,快速 From: https://www.cnblogs.com/towboa/p/17156444.html