55 lines
1.4 KiB
C++
55 lines
1.4 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
//矩阵快速幂
|
||
typedef long long LL;
|
||
const int MOD = 1e9 + 7;
|
||
const int N = 110;
|
||
LL n, k; //本题数据范围很大，用int直接wa哭了
|
||
|
||
//矩阵声明
|
||
struct JZ {
|
||
LL m[N][N];
|
||
} A, res, base;
|
||
|
||
//矩阵乘法
|
||
inline JZ mul(JZ A, JZ B) {
|
||
JZ C;
|
||
memset(C.m, 0, sizeof(C.m));
|
||
for (LL i = 0; i < n; i++)
|
||
for (LL j = 0; j < n; j++)
|
||
for (LL k = 0; k < n; k++) {
|
||
C.m[i][j] += (A.m[i][k] % MOD) * (B.m[k][j] % MOD);
|
||
C.m[i][j] %= MOD;
|
||
}
|
||
return C;
|
||
}
|
||
|
||
void qmi() {
|
||
//将结果矩阵初始化为单位矩阵
|
||
memset(res.m, 0, sizeof res.m);
|
||
for (int i = 0; i < n; i++) res.m[i][i] = 1;
|
||
//其实就是把整数快速幂修改为矩阵快速幂
|
||
while (k) { //二进制快速幂
|
||
if (k & 1) res = mul(res, A); // 联想一下整数快速幂
|
||
A = mul(A, A); // base 翻倍
|
||
k >>= 1;
|
||
}
|
||
}
|
||
int main() {
|
||
cin >> n >> k;
|
||
//输入原始矩阵
|
||
for (int i = 0; i < n; i++)
|
||
for (int j = 0; j < n; j++)
|
||
cin >> A.m[i][j];
|
||
|
||
//计算矩阵快速幂
|
||
qmi();
|
||
|
||
//输出
|
||
for (int i = 0; i < n; i++) {
|
||
for (int j = 0; j < n; j++)
|
||
cout << res.m[i][j] << " ";
|
||
cout << endl;
|
||
}
|
||
return 0;
|
||
} |