题解 | #斐波那契数列#

矩阵快速幂写法，时间复杂度O(logn)

void mul(int a[2], int b[2], int c[][2]){
        int temp[2] = {0};
        for(int i = 0; i < 2; i ++ ){
            for(int j = 0; j < 2; j ++ ){
                temp[i] += a[j] * c[j][i];
            }
        }
        memcpy(b, temp, sizeof temp);
    }
    
    void mul(int a[][2], int b[][2], int c[][2]){
        int temp[2][2] = {0};
        for(int i = 0; i < 2; i ++ ){
            for(int j = 0; j < 2; j ++ ){
                for(int k = 0; k < 2; k ++ ){
                    temp[i][j] += a[i][k] * c[k][j];
                }
            }
        }
        memcpy(b, temp, sizeof temp);
    }
    
    int Fibonacci(int n) {
        int f1[] = {1, 1};
        int a[][2] = {
            {0, 1},
            {1, 1}
        };
        if(n == 1) return 1;
        else if(n == 2) return 1;
        n -= 2;
        while(n){
            if(n & 1) mul(f1, f1, a);
            mul(a, a, a);
            n >>= 1;
        }
        return f1[1];
    }