#include<stdio.h> #define MAXN 100 __int64 map[MAXN][MAXN]; __int64 tmp1[MAXN][MAXN]; __int64 tmp2[MAXN][MAXN]; void fun(__int64 map[MAXN][MAXN],int n,int k) //求矩阵map的k次幂,n代表每一维的数据个数 { int i,j,m; k--; //求map的k次幂,那map还需乘以map的k-1次幂 for(i=1;i<=n;i++) //初始化tmp1数组,tmp1数组记录的是map的2^x次幂 for(j=1;j<=n;j++) tmp1[i][j]=map[i][j]; while(k) { if(k%2) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) tmp2[i][j]=map[i][j]; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { map[i][j]=0; for(m=1;m<=n;m++) { map[i][j]=(map[i][j]+tmp2[i][m]*tmp1[m][j]); } } } for(i=1;i<=n;i++) for(j=1;j<=n;j++) tmp2[i][j]=tmp1[i][j]; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { tmp1[i][j]=0; for(m=1;m<=n;m++) { tmp1[i][j]=(tmp1[i][j]+tmp2[i][m]*tmp2[m][j]); } } k/=2; } } int main(void) { int T; // freopen("d:\\in.txt","r",stdin); scanf("%d",&T); while(T--) { int n,k,i,j; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%I64d",&map[i][j]); fun(map,n,k); } return 0; }