백준 2749번 : 피보나치 수 3 - 분할정복을 이용한 거듭제곱 C++

https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

#include <bits/stdc++.h>

using namespace std;
const int mod =1'000'000;
struct Fibo{
    long long arr[2][2] = {{1, 1}, {1,0}};

    Fibo(){
        arr[0][0] = 1;
        arr[0][1] = 1;
        arr[1][0] = 1;
        arr[1][1] = 0;
    };

    Fibo mutiple(Fibo b){
        long long tmp[2][2] = {{0, 0}, {0, 0}};
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    tmp[i][k] += (arr[i][j] * b.arr[j][k])%mod;
                    tmp[i][k] %= mod;
                }
            }
        }

        Fibo ret = Fibo();
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                ret.arr[i][j] = tmp[i][j];
            }
        }

        return ret;
    }

    void baseMultiple(){
        long long res[2][2] = {{0,0}, {0, 0}};
        long long tmp[2][2] = {{1, 1}, {1,0}};
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    res[i][k] += (arr[i][j] * tmp[j][k])%mod;
                    res[i][k] %= mod;
                }
            }
        }

        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                arr[i][j] = res[i][j];
            }
        }
    }
};

int cnt = 0;
long long N;
Fibo doubleSquare(Fibo cur, long long n){
    if(n==1){
        return cur;
    }

    Fibo tmp = doubleSquare(cur, n/2);
    Fibo ret = tmp.mutiple(tmp);

    if(n%2){
        ret.baseMultiple();
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    Fibo st = Fibo();

    Fibo fb = doubleSquare(st, N);

    cout << fb.arr[1][0] << '\n';
    return 0;
}