피보나치 수 를 log2(N) 빠르기로 구하기.

일반적으로 구하는 피보나치 수는 O(N)이다. 

그런데

 

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

2749번: 피보나치 수 3

n이 1,000,000,000,000,000,000이따구면 어떻게 풂?

 

 

행렬 곱셈을 이용해서 빠르게 구해보자.

일단 F0 = 0 F1 = 1 F2 = 1 F3 = 2 F4 = 3 ........이다.

피보나치의 행렬 곱셈은 이 두 식이 핵 중요하다.

 

그러면 F13 은 어떻게 구하냐?

1. 13을 1까지 쪼갠다.

 

13 -> 12 -> 6 -> 3 -> 2 -> 1

    -1     /2     /2    -1   -1

 

2. 초기 행렬식인

부터 시작해 
기존에 구한 -1 -> /2 -> /2 -> -1 -> -1 을 거꾸로 해주면 된다.

즉, +1 -> +1 -> *2 -> *2 -> +1 이렇게 말이다.

 

이제 2749번을 풀어보자.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long int
#define MOD 1000000
using namespace std;
 
 
int arr[100000];
int arr_size = 0;
 
void flow(ll n)
{
    if (n == 1)
        return;
 
    if (n % 2 == 0)
    {
        arr[arr_size++] = 2;
        flow(n / 2);
    }
    else
    {
        arr[arr_size++] = 1;
        flow(n - 1);
    }
}
 
ll go(int cnt, ll a, ll b, ll c, ll d)
{
    if (cnt == -1)
        return b;
 
    if (arr[cnt] == 1) // +
        return go(cnt - 1, (a + b) % MOD, a, (c + d) % MOD, c);
    else
        return go(cnt - 1, (a * a + b * c) % MOD, (a * b + b * d) % MOD, (a * c + c * d) % MOD, (b * c + d * d) % MOD);
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    ll n;
    cin >> n;
    flow(n);
 
    cout << go(arr_size-1, 1, 1, 1, 0);
 
}

 

 

피사노주기로 푸는 방법이 있긴 한데 머리의 부족함으로 나중에 보자;;;;