백준 - 11444 피보나치 수열 6

 

해결과정 - 분할정복

피보나치 수열을 행렬식으로 나타내면 ((1,1),(1,0))의 제곱꼴로 나타낼 수 있다 이를 이용하여 이 행렬의 제곱을 구하면 logn시간안에 해결이 가능해 진다.

 

이 문제를 풀기위해서는 단위행렬 * M = M 같이 행렬의 곱셈규칙을 알아야 되고 빠른 거듭제곱을 하는 방법을 알아야 된다

빠른 거듭제곱은 30번 거듭제곱을 해야한다 했을때 이를 16 + 8 + 4 + 2 + 1로 만들어 30번이 아닌 5번의 곱셈을 통해 해결하는 방식이다

 

#include <bits/stdc++.h>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

vector<vector<ll>> matrix = { {1, 1}, {1, 0} };

vector<vector<ll>> multiplyMatrix(const vector<vector<ll>>& matrix1,const vector<vector<ll>>& matrix2) {
    vector<vector<ll>> result;
    result.resize(2, vector<ll>(2, 0));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                result[i][j] += matrix1[i][k] * matrix2[k][j];
                result[i][j] %= 1000000007;
            }
        }
    }
    return result;
}

void fastMM(ll n) {
    vector<vector<ll>> result;
    result = { {1, 0}, {0, 1} };

    while (n > 0) {
        if (n & 1) {
            result = multiplyMatrix(matrix, result);
        }
        matrix = multiplyMatrix(matrix, matrix);
        n >>= 1;
    }

    cout << result[0][1] << '\n';
}

int main() {
    FAST;

    ll n;
    cin >> n;

    fastMM(n);
    
    return 0;
}

 

후기

일반항으로 풀수도 있겠지만 이정도 만으로도 정말 대단한 발전인거 같다