题解——洛谷P3390 【模板】矩阵快速幂（矩阵乘法）

模板题

留个档

#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MOD = 1e9+7;

int n,k;
struct Matrix{
  static const int MAXN = 110;
  int n,m;
  int alpha[MAXN][MAXN];
  void init2(void){
    for(int i=0;i<MAXN;i++)
      for(int j=0;j<MAXN;j++)
        alpha[i][j]=0;
    n=m=0;
  }
  void init(int x){
    for(int i=1;i<=x;i++)
      alpha[i][i]=1;
    n=m=x;
  }
  bool can(Matrix b){
    if(m==b.n)
      return true;
    else
      return false;
  }
  Matrix operator * (Matrix b){
    Matrix c;
    c.init2();
    for(int i=1;i<=n;i++){
      for(int j=1;j<=b.m;j++){
        for(int k=1;k<=m;k++)
          c.alpha[i][j]=(c.alpha[i][j]%MOD+alpha[i][k]*b.alpha[k][j]%MOD)%MOD;
      }
    }
    c.n=n;
    c.m=b.m;
  return c;
  }
};
Matrix pow(Matrix a,int p){
  Matrix ans;
  ans.init2();
  ans.init(a.n);
  while(p){
    if(p&1)
      ans=ans*a;
    a=a*a;
    p>>=1;
  }
  return ans;
}
signed main(){
  scanf("%lld %lld",&n,&k);
  Matrix y;
  y.init2();
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      scanf("%lld",&y.alpha[i][j]);
  y.n=y.m=n;
  Matrix x=pow(y,k);
  for(int i=1;i<=x.n;i++){
    for(int j=1;j<=x.m;j++)
      printf("%lld ",x.alpha[i][j]%MOD);
    printf("
");
    }
  return 0;
}