백준 11444 - 피보나치 수 6

출처 : https://www.acmicpc.net/problem/11444 

11444번: 피보나치 수 6

 

고려사항

• 행렬곱을 이용하여 피보나치 수 구하기. (logN 속도를 띈다)
• 피보나치를 푸는 방법이 정말 다양한다...백준 블로그 참조
• 행렬곱을 Divide & Conquer 를 활용하여 구현하면, 엄청난 수의 행렬 제곱도 빠르게 구할 수 있다.
• 백준 02749번 풀이도 확인해 보자!

 

#include <iostream>
using namespace std;

void multi(long long m1[][2], long long m2[][2]){
    long long tmp[2][2];
    long long temp;

    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            temp = 0;
            for(int k=0;k<2;++k){
                temp += (m1[i][k] * m2[k][j]);
            }
            tmp[i][j] = temp % 1000000007;
        }
    }

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

    return;
}

int main() {
    long long mat[2][2] = {1, 1, 1, 0};
    long long res[2][2] = {1, 0, 0, 1};
    long long n;

    cin>>n;
    while(n > 0){
        if(n % 2 == 1){
            multi(res, mat);
        }

        n /= 2;
        multi(mat, mat);
    }

    cout<<res[1][0];
}