백준 11444번 : 피보나치 수 6

• Solved.ac 기준 : 골드 2
• 사용언어 C++

문제 해석 및 풀이

• 행렬 거듭제곱(matrix exponentiation)을 이용

#include <iostream>
#include <vector>
using namespace std;

const int Mod = 1000000007;

typedef vector<vector<long long>> matrix;

matrix multiply(const matrix& a, const matrix& b) {
    matrix c(2, vector<long long>(2));
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            c[i][j] = 0;
            for (int k = 0; k < 2; ++k) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % Mod;
            }
        }
    }
    return c;
}

matrix matrix_pow(matrix a, long long n) {
    matrix result = { {1, 0}, {0, 1} };
    while (n > 0) {
        if (n % 2 == 1) {
            result = multiply(result, a);
        }
        a = multiply(a, a);
        n /= 2;
    }
    return result;
}

long long fibonacci(long long n) {
    if (n == 0) return 0;
    matrix F = { {1, 1}, {1, 0} };
    matrix result = matrix_pow(F, n - 1);
    return result[0][0];
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    long long n;
    cin >> n;
    cout << fibonacci(n) << endl;

    return 0;
}