斐波那契数列的矩阵解法（C）

#include <stdio.h>

#define MOD 1000000007

typedef struct {
    long long a;
    long long b;
    long long c;
    long long d;
} Matrix;


Matrix multiply(Matrix m1, Matrix m2) {
    Matrix result;
    result.a = (m1.a * m2.a + m1.b * m2.c) % MOD;
    result.b = (m1.a * m2.b + m1.b * m2.d) % MOD;
    result.c = (m1.c * m2.a + m1.d * m2.c) % MOD;
    result.d = (m1.c * m2.b + m1.d * m2.d) % MOD;
    return result;
}


Matrix matrixPower(Matrix base, int n) {
    Matrix result = { 1, 0, 0, 1 }; 
    while (n > 0) {
        if (n % 2 == 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        n /= 2;
    }
    return result;
}

long long fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    Matrix base = { 1, 1, 1, 0 };
    Matrix result = matrixPower(base, n - 1);
    return result.a; 
}

int main() {
    int n;
    
    scanf("%d", &n);
    printf("%lld\n", fibonacci(n));
    return 0;
}

}