c++快速幂矩阵乘法完整程序

下面是一个完整的使用快速幂矩阵乘法求解矩阵幂的 C++ 程序，以斐波那契数列为例：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1005;

struct Matrix {
    int n, m;
    int mat[MAXN][MAXN];

    Matrix() {}

    Matrix(int _n, int _m) {
        n = _n, m = _m;
        memset(mat, 0, sizeof(mat));
    }

    void init() {
        for (int i = 1; i <= n; i++) {
            mat[i][i] = 1;
        }
    }

    Matrix operator * (const Matrix &b) const {
        Matrix res(n, b.m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= b.m; j++) {
                for (int k = 1; k <= m; k++) {
                    res.mat[i][j] = (res.mat[i][j] + 1LL * mat[i][k] * b.mat[k][j]) % MOD;
                }
            }
        }
        return res;
    }
};

Matrix qpow(Matrix a, int b) {
    Matrix res(a.n, a.m);
    res.init();
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;

    Matrix A(2, 2);
    A.mat[1][1] = A.mat[1][2] = A.mat[2][1] = 1;

    Matrix ans = qpow(A, n - 1);
    cout << ans.mat[1][2] << endl;

    return 0;
}

在上面的程序中，我们定义了一个 `Matrix` 类，并实现了快速幂矩阵乘法和初始化单位矩阵的函数。然后，我们输入了一个数 $n$，构造了一个 $2\times 2$ 的矩阵 $A$，并使用快速幂矩阵乘法求解 $A^{n-1}$，最后输出答案 $F_n$。