题解 | #矩阵幂#

#include <cstdio>
#include <iostream>

using namespace std;

//感觉重载乘法之后，直接套用快速幂就行了 

//本题需要提供初始化为单位矩阵的手段 

const int MAXN = 10+2;

class Matrix{
public:
	int matrix[MAXN][MAXN];
	int row;
	int col;
	Matrix(int r, int c):row(r),col(c){//初始化为单位矩阵 
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				if(i == j){
					matrix[i][j] = 1;
				}else{
					matrix[i][j] = 0;
				}
			}
		}
	}
	void Input(void){
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				scanf("%d",&matrix[i][j]);
			}
		}
	}
	void Output(void){
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				printf("%d",matrix[i][j]);
				if(j!=col-1){
					printf(" ");
				}
			}
			printf("\n");
		}
	}
	Matrix operator*(const Matrix &m) const {
		Matrix ans(row,m.col);
		if(col != m.row){
			printf("Error!\n");
			exit(0);
		}
		for(int i=0; i<row; i++){
			for(int j=0; j<m.col; j++){
				ans.matrix[i][j] = 0;
				for(int k=0; k<col; k++){
					ans.matrix[i][j] += matrix[i][k] * m.matrix[k][j];
				}
			}
		}
		return ans;
	}
	void operator*=(const Matrix &m){
		Matrix ans = *this * m;
		*this = ans;
	}
};

Matrix Quickpowermatrix(Matrix M, int n){
	if(M.row != M.col){
		printf("Error!\n");
		exit(0);
	}
	Matrix ans(M.row,M.col);
	while(n){
		if(n%2){
			ans *= M;
		}
		M *= M;
		n /= 2;
	}
	return ans;
}

int main(){
	int size, n;
	while(scanf("%d%d",&size, &n) != EOF){
		Matrix M(size, si***put();
		Quickpowermatrix(M, n).Output();
	}
	return 0;
}