3043.큰 N에 대한 피보나치 수

N번째 피보나치 수 FNFN​(F0=0F0​=0, F1=1F1​=1 , Fn=Fn−1+Fn−2Fn​=Fn−1​+Fn−2​) 을 모듈로MM으로 구한다.
NN이 매우 클 수 있다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

ll m; 

struct Matrix {
    ll mat[2][2];
    Matrix() {
        mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
    }
};

Matrix mul(Matrix a, Matrix b) {
    Matrix ans;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
            }
        }
    }
    return ans;
}

Matrix power(Matrix a, ll n) {
    Matrix ans;
    ans.mat[0][0] = 1 % m; ans.mat[1][1] = 1 % m; 

    if (n == 0) return ans;
    if (n == 1) {
        a.mat[0][0] %= m; a.mat[0][1] %= m;
        a.mat[1][0] %= m; a.mat[1][1] %= m;
        return a;
    }

    Matrix half = power(a, n / 2);

    if (n % 2 == 0) {
        return mul(half, half);
    } else {
        return mul(mul(half, half), a);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n;
    if (!(cin >> n >> m)) return 0; 
    
    Matrix T;
    T.mat[0][0] = 1; T.mat[0][1] = 1;
    T.mat[1][0] = 1; T.mat[1][1] = 0;

    cout << power(T, n).mat[0][1] % m;

    return 0;
}

2x2 행렬을 다루기 위해 구조체 선언 후 2행 2열짜리 방이 채워진 배열 선언 두 행렬을 곱해주는 함수를 만든뒤

n번 다 곱하지 말고, 지수를 딱 절반으로 나눠서 한 번만 구한다. 만약 지수가 짝수 half끼리 곱해줌

만약 지수가 홀수 원래 행렬 a를 한 번 더 곱해준다.

그 후 main 함수에서 아까 위에서 말한 피보나치 전용 기본 행렬 T를 조립

T를 n번 거듭제곱한 다음, 0행 1열에 들어있는 피보나치 수를 가져와서 출력