백준 11444번 피보나치 수 6 — 행렬 거듭제곱 C++ 풀이

#include <iostream>
#include <array>

using namespace std;

constexpr long long MOD = 1'000'000'007;
using Matrix = array<array<long long, 2>, 2>;

Matrix multiply(const Matrix& a, const Matrix& b) {
    Matrix result{};

    for (int row = 0; row < 2; ++row) {
        for (int col = 0; col < 2; ++col) {
            for (int mid = 0; mid < 2; ++mid) {
                result[row][col] += a[row][mid] * b[mid][col];
                result[row][col] %= MOD;
            }
        }
    }

    return result;
}

Matrix matrix_power(Matrix base, long long exponent) {
    Matrix result{};
    result[0][0] = 1;
    result[1][1] = 1;

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        exponent /= 2;
    }

    return result;
}

int main() {
    long long n;
    cin >> n;

    Matrix fibonacci{};
    fibonacci[0] = {1, 1};
    fibonacci[1] = {1, 0};
    Matrix result = matrix_power(fibonacci, n);

    cout << result[0][1] << '\n';

    return 0;
}