[ 백준 ] 2749번 - 피보나치 수 3 (C++)

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

2749번: 피보나치 수 3

 

 

[ 문제풀이 ]

 

1. 아래의 식을 바탕으로 $F_{n}$의 값을 구할 수 있습니다.

 

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

 

2. 분할 정복을 활용하여 n이 2의 배수라면 $F_{n} = F_{\frac{n}{2}}\times F_{\frac{n}{2}}$ 아니라면 $F_{n-1}\times F_{1}$을 통해 구해줍니다.

 

3. 메모이제이션을 활용하여 각각의 $F_{i}$을 1,000,000으로 나눈 나머지 값을 저장합니다.

 

4. $F_{n}$의 [0, 1] 항을 출력해 줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<map>
#define M 1000000
#define ll long long
 
using namespace std;
 
ll n;
vector<vector<ll>> mat = { {1,1},{1,0} };
map<ll, vector<vector<ll>>> m;
 
vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b)
{
    vector<vector<ll>> ret = { {0,0},{0,0} };
 
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ret[i][j] = (((a[i][0] % M) * (b[0][j] % M)) % M + ((a[i][1] % M) * (b[1][j] % M)) % M) % M;
        }
    }
 
    return ret;
}
 
vector<vector<ll>> conquer(ll n)
{
    if (m[n].size() != 0) return m[n];
    if (n == 1) return mat;
    if (n == 0) return { {1,0},{0,1} };
    if (n % 2 == 0) {
        return m[n] = mul(conquer(n / 2), conquer(n / 2));
    }
    else {
        return m[n] = mul(conquer(n - 1), conquer(1));
    }
}
 
int main()
{
    scanf("%lld", &n);
 
    vector<vector<ll>> ans = conquer(n);
    
    printf("%d", ans[0][1]);
}