[PS] 백준 2749번: 피보나치 수 3 / 11444번: 피보나치 수 6

 

피보나치 수 3 피보나치 수 6

 

인풋이 100경이다보니깐 O(N)으로만 해도 분명히 타임아웃이 날거라고 생각했다.

100경을 다 훑을순 없고, 100만으로 나눈 나머지만 출력하라니 대충 규칙이 있겠거니 싶었다.

 

여러가지 숫자로 실험하며 확인해보니

어떤 숫자 M으로 나눈 나머지로 피보나치를 하면

M - 1,    1,    0,    1,    1,    2,    3, ...

이런 구간이 존재하는 듯 했다.

 

미리 "M - 1,    1"이 나올때까지의 피보나치 수열을 만들어 두고

Fibonacci[N % 주기]를 출력하면 끝.

 

끝인줄 알았는데 0ms안에 끝나는 다른 사람들 답을 보고 답을 찾아봤다.

피보나치 수를 구하는 여러가지 방법

 $\begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix} = \begin{pmatrix} 1&1\\1&0 \end{pmatrix} ^ n$

이런 기막힌 식이 있더라. 식 자체는 너무 당연한데 이걸 어떻게 생각해내야지 싶다...

 

아무튼 행렬제곱 풀 때 풀었던 코드 그대로 이용해서 갖고오니 0ms안에 해결. 같은 코드로 11444번: 피보나치 6도 처리했다.

 

주기 이용하여 푼 228ms 걸린 코드뭉치

#include <bits/stdc++.h>
#include <unordered_map>

#define FOR(i, n) for(int i = 0; i < int(n); i++)
#define FORL(e, s) for(auto &e : s)
#define endl "\n"
#define vi vector<int>

using namespace std;

unordered_map<long long, int> um;

int modby = 1000000;
long long period = -1;

int main() {
    long long N; cin >> N;
    um[0] = 0, um[1] = 1;

    for(long long depth = 2;; depth++) {
        um[depth] = (um[depth - 1] + um[depth - 2]) % modby;
        if(um[depth] == modby - 1) {
            period = depth + 2;
            um[depth + 1] = 1;
            break;
        }
    }

    cout << um[N % period] << endl;
    return 0;
}

 

행렬 제곱 이용하여 푼 코드

#include <bits/stdc++.h>

#define FOR(i, n) for(int i = 0; i < int(n); i++)
#define FORL(e, s) for(auto &e : s)
#define endl "\n"
#define vll vector<long long>

using namespace std;

long long modby = 1000000007;

vll mult(vll &v1, vll &v2) {
    vector<long long> res(2 * 2, 0);
    FOR(i, 2)
        FOR(j, 2)
            FOR(k, 2)
                res[i * 2 + j] += v1[i * 2 + k] * v2[k * 2 + j];

    FORL(e, res) e = e % modby;            
    return res;    
}

int main() {
    long long N; cin >> N;
    vll V = { 1, 1, 1, 0 };

    vector<vll> vvll; vvll.push_back(V);
    for(long long i = 1; i < N; i *= 2) 
        vvll.push_back(move(mult(vvll.back(), vvll.back())));


    V = { 1, 0, 0, 1};
    long long limit = N;
    while (limit > 0) {
        long long idx = 0;
        while(true) {
            if(static_cast<long long>(pow(2, idx + 1)) > limit) {
                V = move(mult(V, vvll[idx]));
                limit -= static_cast<long long>(pow(2, idx));
                break;
            }
        idx += 1;
        }
    }

    cout << V[1] << endl;
}