Baekjoon 2749 (피보나치 수 3)

Baekjoon 2749, 백준 2749 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <iostream>
#include <vector>
using namespace std;

int N = 2;

vector<vector<long long>> multiply_matrix(vector<vector<long long>> &v1, vector<vector<long long>> &v2) {
    // calculate v1 * v2
    vector<vector<long long>> ans;

    for(int i = 0; i < N; i++){
        vector<long long> temp;
        for(int j = 0; j < N; j++){
            long long int val = 0;
            for(int k = 0; k < N; k++){
                val += ((v1[i][k] % 1000000) * (v2[k][j] % 1000000)) % 1000000;
            }
            val %= 1000000;
            temp.push_back(val);
        }
        ans.push_back(temp);
    }

    return ans;
}

vector<vector<long long>> pow_matrix(vector<vector<long long>> &v, long long int B){
    if(B == 1) {
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                v[i][j] %= 1000000;
            }
        }
        return v;
    }
    else if(B % 2 == 0) {
        vector<vector<long long>> temp1 = pow_matrix(v, B/2);
        vector<vector<long long>> temp2 = multiply_matrix(temp1, temp1);
        return temp2;
    }
    else {
        vector<vector<long long>> temp1 = pow_matrix(v, B/2);
        vector<vector<long long>> temp2 = multiply_matrix(temp1, temp1);
        vector<vector<long long>> temp3 = multiply_matrix(v, temp2);
        return temp3;
    }
}

int main() {
    long long int n;
    cin >> n;

    // input array [[1,1],[1,0]]
    vector<vector<long long>> arr;
    vector<long long> temp;
    temp.push_back(1);
    temp.push_back(1);
    arr.push_back(temp);
    temp.pop_back();
    temp.push_back(0);
    arr.push_back(temp);

    // multiply
    if(n <= 1) {
        cout << n << '\n';
        return 0;
    }
    vector<vector<long long>> ans;
    ans = pow_matrix(arr, n-1);

    // print
    cout << ans[0][0] << '\n';

}

피보나치 수를 [ [1, 1] , [1, 0] ] 의 2 * 2 행렬의 거듭제곱으로 구할 수 있음을 이용하였다!
행렬은 기본적으로 vector> 으로 사용하였으며,
행렬 거듭제곱 & 곱셈을 분할정복으로 처리하였다.