题解 | #斐波那契数列#

typedef struct _Matrix{
    int a, b, c, d;
}Matrix;

Matrix matrix_mutiply(Matrix &x, Matrix &y){
    Matrix z;
    z.a = x.a * y.a + x.b * y.c;
    z.b = x.a * y.b + x.b * y.d;
    z.c = x.c * y.a + x.d * y.c;
    z.d = x.c * y.b + x.d * y.d;
    return z;  
}

Matrix quick_matrix_pow(Matrix &x, int n){
    Matrix ans{1, 0, 0, 1};
    while(n){
        if(n & 1) ans =matrix_mutiply(ans, x);
        x = matrix_mutiply(x, x);
        n >>= 1;
    }
    return ans;
}

class Solution {
public:
    int Fibonacci(int n) {
        Matrix x{1, 1, 1, 0};
        Matrix ans = quick_matrix_pow(x, n - 1);
        return ans.a;
    }
};