【C++】21行矩阵快速幂

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0) return 0; 
        vector<vector<int>> power{{1, 1}, {1, 0}}; //用于记录当前快速幂
        vector<vector<int>> result{{1, 0}, {0, 1}}; //用于记录最终结果
        while(n > 0) { //
            if(n & 1) matrixProduct(result, power); //将n视为二进制取最后一比特，若为1则将对应快速幂乘到结果上
            matrixProduct(power, power); //快速幂自乘
            n >>= 1; //比特右移
        }
        return result[1][0]; //由于F(1)=1, F(0)=0，直接取[1][0]即可
    }
    void matrixProduct(vector<vector<int>> &m1, vector<vector<int>> m2) {
        vector<vector<int>> temp = m1; //为了计算时不改变数值拷贝一份m1，计算结果直接在m1里修改
        for(int i = 0; i <= 1; i++) {
            for(int j = 0; j <= 1; j++) 
                m1[i][j] = temp[i][0] * m2[0][j] + temp[i][1] * m2[1][j];
        }
    }
};