-
Notifications
You must be signed in to change notification settings - Fork 105
Expand file tree
/
Copy path6.12.cpp
More file actions
86 lines (77 loc) · 2.13 KB
/
6.12.cpp
File metadata and controls
86 lines (77 loc) · 2.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/*
* 题目名称：计算两个矩阵的乘积
* 题目来源：北京邮电大学复试上机题
* 题目链接：http://t.cn/Aip4T3HX
* 代码作者：杨泽邦(炉灰)
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100;
struct Matrix {
int matrix[MAXN][MAXN];
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;
}
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) {
if (k % 2 == 1) { //不断将k转换为二进制
answer = Multiply(answer, x);
}
k /= 2;
x = Multiply(x, x); //x不断平方
}
return answer;
}
void InputMatrix(Matrix &x) { //矩阵输入
for (int i = 0; i < x.row; ++i) {
for (int j = 0; j < x.col; ++j) {
scanf("%d", &x.matrix[i][j]);
}
}
}
void OutputMatrix(Matrix x) { //矩阵输出
for (int i = 0; i < x.row; ++i) {
for (int j = 0; j < x.col; ++j) {
if (j == 0) {
printf("%d", x.matrix[i][j]);
} else {
printf(" %d", x.matrix[i][j]);
}
}
printf("\n");
}
return ;
}
int main() {
int n, k;
while (scanf("%d%d", &n, &k) != EOF) {
Matrix x(n, n);
InputMatrix(x);
Matrix answer = FastExponentiation(x, k);
OutputMatrix(answer);
}
return 0;
}