题解 | #矩阵幂#

//土尔逊Torson 编写于2023/05/18
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>

using namespace std;

struct Matrix {
	int matrix[10][10];
	int row, col;
	Matrix(int r,int c) : row(r), col(c) {}
};

Matrix Multiply(Matrix x, Matrix y) {
	Matrix answer(x.row, y.col);
	for (int i = 0; i < answer.row; ++i) {
		for (int j = 0; j < answer.col; ++j) {
			answer.matrix[i][j] = 0;
			for (int k = 0; k < x.col; ++k) {
				answer.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
			}
		}
	}
	return answer;
}

void PrintMatrix(Matrix x) {
	for (int i = 0; i < x.row; ++i) {
		for (int j = 0; j < x.col; ++j) {
			if (j != 0) {
				printf(" ");
			}
			printf("%d", x.matrix[i][j]);
		}
		printf("\n");
	}
	return;
}

Matrix FastExponentiation(Matrix x, int k) {    //快速幂矩阵计算
	Matrix answer(x.row, x.col);
	for (int i = 0; i < answer.row; ++i) {       //初始化为单位矩阵
		for (int j = 0; j < answer.col; ++j) {
			if (i == j) {
				answer.matrix[i][j] = 1;
			}
			else {
				answer.matrix[i][j] = 0;
			}
		}
	}
	while (k != 0) {                            //不断将k转换为二进制
		if (k % 2 == 1) {                       //累乘x的2^k次幂
			answer = Multiply(answer, x);
		}
		k /= 2;
		x = Multiply(x, x);                     //x不断平方
	}
	return answer;
}

int main() {
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF) {
		Matrix x(n, n);
		for (int i = 0; i < x.row; ++i) {
			for (int j = 0; j < x.col; ++j) {
				scanf("%d", &x.matrix[i][j]);
			}
		}
		Matrix answer = FastExponentiation(x, k);
		PrintMatrix(answer);
	}
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")