矩阵快速幂实现斐波那契数列c++

以下是使用矩阵快速幂实现斐波那契数列的C++代码：

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

typedef long long ll;

const ll mod = 1e9 + 7;

struct matrix {
    ll cell[2][2];
    matrix(ll a, ll b, ll c, ll d) {
        cell[0][0] = a;
        cell[0][1] = b;
        cell[1][0] = c;
        cell[1][1] = d;
    }
    matrix() {
        memset(cell, 0, sizeof(cell));
    }
};

matrix mul(matrix a, matrix b) {
    matrix r;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                r.cell[i][j] += a.cell[i][k] * b.cell[k][j] % mod;
                r.cell[i][j] %= mod;
            }
        }
    }
    return r;
}

matrix matrixpow(ll k) {
    matrix r(1, 0, 0, 1);
    matrix cm(1, 1, 1, 0);
    while (k) {
        if (k & 1) r = mul(r, cm);
        cm = mul(cm, cm);
        k >>= 1;
    }
    return r;
}

ll fib(ll n) {
    if (n == 0) return 0;
    matrix res = matrixpow(n - 1);
    return res.cell[0][0];
}

int main() {
    ll n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}