斐波那契数列矩阵快速幂算法

斐波那契数列矩阵快速幂算法是一种高效计算斐波那契数列的方法。该算法利用矩阵快速幂的思想，将斐波那契数列的递推式转化为矩阵形式，然后通过矩阵快速幂的方式进行计算。

具体来说，我们可以将斐波那契数列的递推式 F(n) = F(n-1) + F(n-2) 转化为矩阵形式：

| F(n) | | 1 1 | | F(n-1) |
| | = | | * | |
| F(n-1) | | 1 0 | | F(n-2) |

然后，我们可以使用矩阵快速幂的方式，快速计算出这个矩阵的 n 次幂，从而得到 F(n) 的值。

下面是斐波那契数列矩阵快速幂算法的代码实现：

struct Matrix {
    long long mat[2][2];
    Matrix() { memset(mat, 0, sizeof(mat)); }
    Matrix operator*(const Matrix& other) const {
        Matrix res;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    res.mat[i][j] += mat[i][k] * other.mat[k][j];
                }
            }
        }
        return res;
    }
};

long long fib(int n) {
    if (n == 0) return 0;
    Matrix base, res;
    base.mat[0][0] = base.mat[0][1] = base.mat[1][0] = 1;
    res.mat[0][0] = res.mat[1][1] = 1;
    while (n) {
        if (n & 1) res = res * base;
        base = base * base;
        n >>= 1;
    }
    return res.mat[0][1];
}