题解 | #矩阵幂#

#include <bits/stdc++.h>
#define MAX 100
using namespace std;

typedef long long ll;

typedef struct matrix{
	ll data[MAX][MAX];
	matrix(){
		memset(data,0,sizeof(data));
	}
}matrix;

matrix multiply(matrix &a,matrix &b,int n){	//两个矩阵相乘 
	matrix c;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= n; k++){
				c.data[i][j] += a.data[i][k] * b.data[k][j];	
			}
		}
	}
	return c;
}

matrix qmi(matrix &a,ll m,int n){	//n阶矩阵a的m次幂 
	matrix res;
	for(int i = 1; i <= n; i++)
		res.data[i][i] = 1;
	while(m){
		if(m & 1)
			res = multiply(res,a,n);	//相乘 
		a = multiply(a,a,n);	//n矩阵的幂次翻倍
		m >>= 1; 
	}
	return res; 
}



int main(){
	int n,k;
	
	while(cin>>n>>k){
		matrix a;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				cin>>a.data[i][j];
		a = qmi(a,k,n);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)
				cout<<a.data[i][j]<<" ";
			cout<<endl;
		}

	}
}