运行时间16ms,矩阵乘法 + 快速幂
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 32;
int n, k;
int res[N][N], a[N][N];
void mul(int c[][N], int a[][N], int b[][N]) //2维 = 2维 * 2维
{
int temp[N][N] = {0};
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
temp[i][j] = temp[i][j] + (LL)a[i][k] * b[k][j];
//temp[i][j] += 第i行第k列 * 第k行第j列
memcpy(c, temp, sizeof temp);
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> a[i][j];
memcpy(res, a, sizeof a);
k--;
while(k)
{
if(k&1) mul(res, res, a); //res = res * a;
k >>= 1;
mul(a, a, a); //a = a * a;
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout << res[i][j] << ' ';
cout << endl;
}
return 0;
}