[백준] 11444 : 피보나치 수 6

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

11444번: 피보나치 수 6

---

• N 의 범위가 엄청나기 때문에, 반드시 logN 의 알고리즘이 필요하다.
• 피보나치 값을 logN 으로 구하는 방법에는 행렬곱을 이용한 방식이 있다.
• [ 0 1     <- 왼쪽 행렬을 N 제곱 한 결과는 [ n-1  n           각 위치가 피보나치 값을 나타내게 된다.
•   1 1 ]                                                       n   n+1 ]
• n번째 피보나치 값은 행렬을 n 번 곱한 뒤 [0][1] 번째 / [1][0] 번째 위치가 되는 것이다.
• 행렬의 곱은 분할정복이 가능하므로 n 을 2진수로 표현한 뒤 각 자릿수에 해당하는 행렬을 곱해줌으로써 logN 에 계산한다.

---

#include <iostream>

#define ull unsigned long long
#define MOD 1000000007

using namespace std;

ull cur[4] = {0, 1, 1, 1}, mul[4] = {0, 1, 1, 1};

void matmul(ull (&a)[4], ull (&b)[4], ull (&res)[4])    // a, b 는 곱할 행렬, res 는 결과값 담아줄 행렬
{
    ull temp[4];
    temp[0] = ((a[0]*b[0])%MOD + (a[1]*b[2])%MOD)%MOD;  // 행렬곱, 모듈러 연산 적용
    temp[1] = ((a[0]*b[1])%MOD + (a[1]*b[3])%MOD)%MOD;
    temp[2] = ((a[2]*b[0])%MOD + (a[3]*b[2])%MOD)%MOD;
    temp[3] = ((a[2]*b[1])%MOD + (a[3]*b[3])%MOD)%MOD;
    for(int i = 0 ; i < 4 ; i++) res[i] = temp[i];      // 행렬곱 결과를 갱신해줌
}

ull fibonacci(ull n)
{
    ull digit = 1;
    while(n >= digit)
    {
        if(n & digit) matmul(cur, mul, cur);            // 만약 자릿수 겹치면 현재행렬에 제곱행렬 곱해줌
        matmul(mul, mul, mul);                          // 제곱행렬은 매 자릿수마다 제곱됨
        digit = digit << 1;
    }
    return cur[1];
}

int main(void)
{
    ull n;
    cin >> n;
    cout << fibonacci(n-1) << endl;
}