题解 | #矩阵幂#
矩阵幂
http://www.nowcoder.com/practice/31e539ab08f949a8bece2a7503e9319a
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 10;
struct Matrix {
int row, col;
int matrix[MAXN][MAXN];
Matrix(int r, int c) :row(r), col(c) {}
};
Matrix Multiply(Matrix x, Matrix y) {
Matrix ans = Matrix(x.row, y.col);
for (int i = 0; i < ans.row; ++i) {
for (int j = 0; j < ans.col; ++j) {
ans.matrix[i][j] = 0;
for (int k = 0; k < x.col; ++k) {
ans.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
}
}
}
return ans;
}
void CoutMatrix(Matrix x) {
for (int i = 0; i < x.row; ++i) {
for (int j = 0; j < x.col; ++j) {
if (j) {
printf(" ");
}
printf("%d", x.matrix[i][j]);
}
printf("\n");
}
}
Matrix QuickPower(Matrix x, int k) {
Matrix ans = Matrix(x.row, x.col);
for (int i = 0; i < ans.row; ++i) {
for (int j = 0; j < ans.col; ++j) {
ans.matrix[i][j] = i == j ? 1 : 0;
}
}
while (k) {
if (k % 2) {
ans = Multiply(ans, x);
}
k /= 2;
x = Multiply(x, x);
}
return ans;
}
int main() {
int n, k;
while (scanf("%d%d", &n, &k) != EOF) {
Matrix x = Matrix(n, n);
for (int i = 0; i < x.row; ++i) {
for (int j = 0; j < x.col; ++j) {
scanf("%d", &x.matrix[i][j]);
}
}
CoutMatrix(QuickPower(x, k));
}
return 0;
}
