矩阵的快速幂算法c++

矩阵的快速幂算法可以用来求解矩阵的幂，在一些数学和计算机科学领域中经常会用到。C++实现如下：

#include <iostream>
#include <vector>

using namespace std;

// 矩阵快速幂
vector<vector<int>> matrixPow(vector<vector<int>>& matrix, int n) {
    int m = matrix.size();  // 矩阵的行数
    vector<vector<int>> res(m, vector<int>(m, 0));
    for (int i = 0; i < m; i++) {
        res[i][i] = 1;  // 初始化为单位矩阵
    }
    while (n > 0) {
        if (n & 1) {
            vector<vector<int>> tmp(m, vector<int>(m, 0));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < m; j++) {
                    for (int k = 0; k < m; k++) {
                        tmp[i][j] += res[i][k] * matrix[k][j];
                    }
                }
            }
            res = tmp;
        }
        vector<vector<int>> tmp(m, vector<int>(m, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < m; k++) {
                    tmp[i][j] += matrix[i][k] * matrix[k][j];
                }
            }
        }
        matrix = tmp;
        n >>= 1;
    }
    return res;
}

int main() {
    vector<vector<int>> matrix = {{1, 2}, {3, 4}};
    int n = 3;
    vector<vector<int>> res = matrixPow(matrix, n);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[0].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

在上面的程序中，`matrixPow`函数用来计算矩阵`matrix`的`n`次幂，并返回结果`res`。在`while`循环中，通过位运算来计算`n`的二进制表示，如果`n`的二进制表示的最后一位是1，则将`res`与`matrix`相乘得到新的`res`；否则，将`matrix`自乘得到新的`matrix`。最后返回`res`即可。

在`main`函数中，我们使用下面的代码调用`matrixPow`函数，并打印结果。

vector<vector<int>> matrix = {{1, 2}, {3, 4}};
int n = 3;
vector<vector<int>> res = matrixPow(matrix, n);
for (int i = 0; i < res.size(); i++) {
    for (int j = 0; j < res[0].size(); j++) {
        cout << res[i][j] << " ";
    }
    cout << endl;
}

这样就可以输出矩阵`matrix`的`n`次幂了。