矩阵连乘的快速实现

矩阵快速幂 例子 斐波那契数列 https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/solutions/976888/fei-bo-na-qi-shu-lie-by-leetcode-solutio-hbss/

矩阵幂次乘：

vector<vector<long>> q{{1, 1}, {1, 0}};
vector<vector<long>> res = pow(q, n - 1);


vector<vector<long>> pow(vector<vector<long>>& a, int n) {
    vector<vector<long>> ret{{1, 0}, {0, 1}};
    while (n > 0) {
        if (n & 1) {
            ret = multiply(ret, a);
        }
        n >>= 1;
        a = multiply(a, a);
    }
    return ret;
}

vector<vector<long>> multiply(vector<vector<long>>& a, vector<vector<long>>& b) {
    vector<vector<long>> c{{0, 0}, {0, 0}};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
        }
    }
    return c;
}