백준 11444번: 피보나치 수 6

문제

문제 바로가기> 백준 11444번: 피보나치 수 6

풀이

아래와 같이 행렬 곱을 이용하여 O(log n)시간 안에 문제를 해결할 수 있다.

#include<iostream>
#include<vector>
#define MOD 1000000007 
using namespace std;

typedef vector<vector<long long>> matrix;
long long n;

matrix operator *(matrix& a, matrix& b){ // 행렬 곱셈 
    matrix c(2, vector<long long>(2)); // 2칸 만들고, 그 안을 vector<long long>(2)로 채운다
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            for(int k=0; k<2; k++)
                c[i][j] += a[i][k]*b[k][j];
            c[i][j]%=MOD;
        }
    }
    return c;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    matrix a = {{1, 1}, {1, 0}};
    matrix ans = {{1, 0}, {1, 0}};

    while (n>0){
        if(n&1) ans = ans*a;
        a=a*a;
        n>>=1;
    }
    cout << ans[0][1];
}