矩阵的快速幂和整数快速幂类似,只不过初始值是单位矩阵
#include <iostream> using namespace std; struct matrix { int m[10][10]; int row; matrix(int r) { row = r; }; }; matrix multiply(matrix a, matrix b) { matrix ans(a.row); for (int i = 0; i < ans.row; i++) { for (int j = 0; j < ans.row; j++) { ans.m[i][j] = 0; for (int k = 0; k < a.row; k++) { ans.m[i][j] += a.m[i][k] * b.m[k][j]; } } } return ans; } void print(matrix a) { for (int i = 0; i < a.row; i++) { for (int j = 0; j < a.row; j++) { if (j == a.row - 1) { cout << a.m[i][j] << endl; } else { cout << a.m[i][j] << ' '; } } } } matrix fastPower(matrix a, int k) { matrix ans(a.row); for (int i = 0; i < a.row; i++) { for (int j = 0; j < a.row; j++) { if (i == j) ans.m[i][j] = 1; else ans.m[i][j] = 0; } } while (k != 0) { if (k % 2 == 1) { ans = multiply(ans, a); } k /= 2;//右移 a = multiply(a, a); //平方 } return ans; } int main() { int n, k; while (cin >> n >> k) { // 注意 while 处理多个 case // cout << a + b << endl; matrix a(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a.m[i][j]; } } matrix b = fastPower(a, k); print(b); } } // 64 位输出请用 printf("%lld")