BOJ 11444, 피보나치 수 6

이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,000,000,000,000)인 걸 보아 절대 동적 계획법으로는 풀 수 없는 문제입니다. 

이럴 땐, 점화식을 자세히 살펴보고, 분해해보아야 합니다.

수열의 n번째 항과, n-1번째 항을 위 아래로 나열해보면

 

과 같이 나타낼 수 있습니다. 그럼? 이것을 행렬로 나타내보면? 

 

입니다. 오! 개쩔죠? 그럼? 이 점화식을 계속해서 나열해본다면!

이 될 것이고

이렇게 되니까, 피보나치 수열의 일반 행렬을 얻을 수 있습니다.

n by n의 행렬을 곱하는 데엔 보통 O(n^3)의 시간 복잡도가 필요합니다.

그리고 같은 행렬을 M번 곱하는 데는 O(Mn^3)의 시간이 필요하죠. 하지만, 문제에서 요구하는 t의 범위가 20억 (2*10^9)이니 위의 시간복잡도로 풀기엔 아직도 턱없이 부족합니다.

그러므로, 위에 서술한대로 시간 복잡도를 O(N^3logM)으로 줄이기 위해선, 어떤 수의 거듭제곱을 빠르게 구하는 알고리즘인 Fast Power Algorithm을 사용해야합니다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
typedef vector<vector<long long>> matrix;
const LL mod = 1000000007;
 
matrix operator* (const matrix &a, const matrix &b) {
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            for (int k = 0; k<n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
            c[i][j] %= mod;
        }
    }
    return c;
}
 
int main() {
    LL n;
 
    cin >> n;
 
    matrix ans = { { 1, 0 },{ 0, 1 } };
    matrix a = { { 1, 1 },{ 1, 0 } };
 
    while (n > 0) {
        if (n % 2 == 1) {
            ans = ans * a;
        }
        a = a * a;
        n /= 2;
    }
 
    cout << ans[0][1];
 
    return 0;
}