给定n*n的矩阵A,求A^k
行列都是n
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=,MOD=;
typedef long long ll;
inline ll read(){
char c=getchar();ll x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
ll n,k;
struct mat{
ll mt[N][N];
mat(){memset(mt,,sizeof(mt));}
}a,im,ans;
void init(){
for(int i=;i<=n;i++) im.mt[i][i]=;
}
mat mul(mat &a,mat &b){
mat c;
for(int i=;i<=n;i++)
for(int k=;k<=n;k++) if(a.mt[i][k])
for(int j=;j<=n;j++)
c.mt[i][j]=(c.mt[i][j]+a.mt[i][k]*b.mt[k][j])%MOD;
return c;
}
void pow(mat &a,ll b){
ans=im;
for(;b;b>>=,a=mul(a,a))
if(b&) ans=mul(ans,a);
}
int main(){
n=read();k=read();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) a.mt[i][j]=read();
init();
pow(a,k);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++) printf("%lld ",ans.mt[i][j]);
putchar('\n');
}
}