[BOJ] 백준 11444 - 피보나치 수 6

문제 링크

www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

 

풀이

$n$이 굉장히 큽니다.

 

여러 개의 식들을 하나의 행렬로 표현할 수 있습니다.

$(a, b) \rightarrow (b, a+b)$가 되게끔 적절히 행렬로 표현해봅시다. 관련된 변수가 $a, b$ 두 가지니 2*2 행렬을 생각해볼 수 있습니다.

$$\pmatrix{a & b}\pmatrix{ ? & ? \\ ? & ?} = \pmatrix{b & a+b}$$

$a, b$에 대한 식을 각각 세워봅시다.

$$\begin{cases} a_{n+1} = 0\cdot a_{n} + 1\cdot b_{n} \\ b_{n+1}=1\cdot a_{n} + 1\cdot b_{n}\end{cases}$$

위 두 식의 계수를 행렬로 만들어줍니다. 이 행렬을 $X=\pmatrix{0 & 1\\ 1 & 1}$라 합시다.

 

초기 $a, b$값을 각각 0, 1로 잡아봅시다. $(F_0, F_1)$에 $X$를 한 번 곱해주면 $(F_1, F_2)$가 됩니다. 두 번 곱해주면 $(F_2, F_3)$이 되겠죠?

따라서 $(0, 1)$에 $X^n$을 곱해주면 $F_n$을 구할 수 있습니다.

 

이렇게 점화식을 행렬로 표현하면 $n$번째 항을 구하기 위해 행렬의 $n$ 거듭제곱을 구해주면 되고, 거듭제곱의 구현은 $O(\log{N})$ 복잡도로 최적화할 수 있으므로 $n$번째 항을 빠르게 구할 수 있게 됩니다.

 

백준 10830 - 행렬 제곱 문제와 같은 방식을 이용해 $X^n$을 빠르게 구해주도록 합시다.

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll MOD = 1'000'000'007;

vvll mat = {{0, 1},
            {1, 1}};

vvll matMul(vvll &a, vvll &b) {
    vvll ret(2, vll(2));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                ret[i][j] += a[i][k] * b[k][j];
                ret[i][j] %= MOD;
            }
        }
    }
    return ret;
}

vvll go(ll k) {
    if (k == 1) return mat;
    if (k & 1) {
        vvll res = go(k - 1);
        return matMul(mat, res);
    }
    vvll res = go(k / 2);
    return matMul(res, res);
}

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

    ll n;
    cin >> n;
    vvll res = go(n);
    ll ans = res[1][0];
    cout << ans;
}