[백준 2749번] 피보나치 수 3

문제 링크: https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

<문제 풀이> 수학, 선형대수학, 행렬 거듭제곱

n이 매우 크기 때문에 dp를 이용한 점화식 풀이는 O(N)이므로 해결할 수 없다 따라서 점화식을 행렬로 변환해서 O(M^3 * logN) 시간 복잡도의 빠른 행렬 거듭제곱 알고리즘을 사용해야 한다. 
(이 문제는 피사노 주기도 사용 가능)

 

<피보나치 수 점화식을 행렬로 표현하기>

 

위와 같은 피보나치 수 점화식을 아래와 같이 행렬로 표현할 수 있다.

 

 

이렇게 행렬을 구하면 다음 아래의 행렬을 계산해서 c + d를 하면 Fn+1을 구할 수 있다. 

Fn을 구하기 위해서 다음식의 양변에 n - 1을 대입한다.

그러면 다음과 같은 식을 얻을 수 있다

이제 {{1, 1}, {1, 0}} 행렬의 n-1 거듭제곱을 빠르게 구하면 된다.

(행렬 거듭제곱 알고리즘은 정수 거듭제곱 알고리즘과 똑같이 구현하면 됩니다.)

 

<C++ 소스코드>

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin >> n;
    matrix a = { {1, 1}, {1, 0} };
    matrix res = (power(a, n - 1));
    cout << (res[1][0] + res[1][1]) % 1000000;
    
 
    return 0;
}