백준 11444 - 피보나치 수 6

https://www.acmicpc.net/problem/11444

 

최대 $10^{18}$ 번째 피보나치 항을 구해야 한다.

 

피보나치 수의 n번째 항 $F_{n}$은 다음과 같은 행렬 제곱으로 나타낼 수 있음이 알려져있다.

 

$\begin{pmatrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{pmatrix}^{n}$

 

분할 정복을 이용한 거듭제곱을 활용하여 원하는 항을 빠르게 구하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll mod = 1e9 + 7;
ll n;

struct mat_fibo
{
    vector<vector<ll>> mat;
    
    mat_fibo(): mat(2, vector<ll>(2)) {}

    mat_fibo operator * (mat_fibo &arg)
    {
        mat_fibo ret;

        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    ret.mat[i][j] = (ret.mat[i][j] + mat[i][k] * arg.mat[k][j]) % mod;

        return ret;
    }
};

mat_fibo po(mat_fibo x, ll p)
{
    if (p == 1)
        return x;
    
    if (p & 1)
        return po(x, p - 1) * x;
    
    return po(x * x, p / 2);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    
    if (n <= 1)
    {
        cout << n;
        return 0;
    }

    mat_fibo fib;
    fib.mat[0][0] = fib.mat[0][1] = fib.mat[1][0] = 1;
    fib.mat[1][1] = 0;

    auto res = po(fib, n);

    cout << res.mat[0][1];
}