[백준] [C++] 11444번 피보니치 수 6 (분할정복)

1. 문제

11444번: 피보나치 수 6 (acmicpc.net)

11444번: 피보나치 수 6

 

2. 풀이

이 문제는 엄청나게 큰 n번째 피보나치 수를 구하는 문제이며

 

피보나치 수의 성질을 잘 알고 있어야 풀 수 있는 문제이다.

 

피보나치 수의 점화식은 다음과 같다

 

f_n = f_n-1 + f_n-2,    (f0 = 0, f1 = 1)

 

이 식을 다음과 같이 열벡터로나타낼 수 있다. 

C_n은 원소의 합이 f_n이 되는 열벡터이다.

 

C_n = { {f_n-2},

         {f_n-1}}

 

그리고 이 식을 풀어쓰면 다음과 같은 식이 나오게 된다.

 

C_n = { {f_n-2},

         {f_n-2 + f_n-3} }

 

이 식은 다음과 같이 행렬 곱으로 표현할 수 있다.

 

C_n = { {0, 1}, {1, 1} }  X  { {f_n-3} , {f_n-2} }

 

그러면 이제 다음과 같이 고쳐 쓸 수 있을 것이다                    

 

C_n = { {0, 1}, {1, 1} }  X C_n-1

 

즉 n번째 피보나치의 원소들은 특정 행렬과의 곱으로 결정된다는것이다.

결국 C_n 은 이 행렬들의 제곱으로 표현된다.

 

W = { {0, 1}, {1, 1} } 

 

C_n = W^n-2 X C_2 , (n > 2) 

 

   

이제 분할정복으로 빠르게 행렬을 제곱한뒤, 피보나치 2번째 원소행렬과 곱을하면

큰 수n에 대하여  피보나치 원소들을 구할 수 있고, 이 두 원소를 더하면 피보나치 수를 구할 수 있게된다.

 

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
 
using namespace std;
long long D = 1000000007;
vector<vector<long long> > matrix = { {0, 1} , {1, 1}};
 
vector<vector<long long> > product(vector<vector<long long> >& a, vector<vector<long long> >& b) {
    vector<vector<long long> > ret(a.size(), vector<long long>(b[0].size(), 0)); 
    for(long long i = 0; i < a.size(); i++) {
        for(long long j = 0; j < b[0].size(); j++) {
            for(long long k = 0; k < b.size(); k++) {
                ret[i][j] = (ret[i][j] + (a[i][k]*b[k][j])%D)%D;
            }
        }
    }
    return ret;
}
 
vector<vector<long long> > product(long long b) {
    if(b == 1) {
        return matrix;
    }
    if(b%2 == 0) {
        vector<vector<long long> > tmp = product(b/2);
        return product(tmp, tmp);
    }
    else {
        vector<vector<long long> > tmp = product(b-1);
        return product(tmp, matrix);
    }
}
 
int main() {
    long long n;
    cin>>n;
    if(n == 0) {
        cout<<0;
    }
    else if(n <= 2) {
        cout<<1;
    }
    else {
        vector<vector<long long> > factorial2 = {{0}, {1}};
        vector<vector<long long> > W = product(n-2);
        vector<vector<long long> > answer = product(W, factorial2);
        cout<<(answer[0][0] + answer[1][0])%D;
    }
}