Матричное умножение Фибоначчи

def mat_mult(A, B):
    return [
        [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
        [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
    ]

def mat_pow(M, n):
    result = [[1, 0], [0, 1]]
    while n > 0:
        if n & 1:
            result = mat_mult(result, M)
        M = mat_mult(M, M)
        n >>= 1
    return result

def fib(n):
    if n <= 1:
        return n
    M = [[1, 1], [1, 0]]
    return mat_pow(M, n-1)[0][0]

n = int(input())
print(fib(n))

#include <bits/stdc++.h>
using namespace std;

struct Matrix {
    long long a, b, c, d;
    Matrix(long long a=1, long long b=0, long long c=0, long long d=1) 
        : a(a), b(b), c(c), d(d) {}
};

Matrix multiply(const Matrix& A, const Matrix& B) {
    return Matrix(
        A.a*B.a + A.b*B.c,
        A.a*B.b + A.b*B.d,
        A.c*B.a + A.d*B.c,
        A.c*B.b + A.d*B.d
    );
}

Matrix power(Matrix M, long long n) {
    Matrix result;
    while (n > 0) {
        if (n & 1) result = multiply(result, M);
        M = multiply(M, M);
        n >>= 1;
    }
    return result;
}

long long fib(long long n) {
    if (n <= 1) return n;
    Matrix M(1, 1, 1, 0);
    return power(M, n-1).a;
}

int main() {
    long long n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}