#2749 피보나치 수

 

문제 링크 : https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

 

문제 조건을 딱 보면 알수 있듯이 일반 recursion이나 dp로는 제시간에 불가능하다.

 

책에서 봐서 머릿속에 얼핏 남아있는 아이디어가 문득 생각났다.

 

dp같은 경우 점화식의 형태로 나타내는 경우가 많은데, 이 점화식을 풀고 풀어 단순한 식으로 만들 수 있다.

 

과정은 조금 더 복잡할 수 있지만 프로그램의 실행 속도는 확연히 줄어든다.

 

 

F_n을 n번째 피보나치 수라 한다면,

이라는 행렬의 곱으로 나타낼 수 있다.

 

 

결국 남은 것은 저 2x2 행렬을 k번 거듭제곱 해주는 것인데, k가 짝수면 k/2 를 한번 계산해서 제곱해주고 k가 홀수면
k-1 과 1으로 나누어 계산해주면 된다.

 

시간 내에 통과 가능하다!

 

구현이 막히는 것을 보아하니 많은 노력이 필요할 것 같다.

 

#include <bits/stdc++.h>

using namespace std;

vector<long long> base{2, 1, 1, 1};
long long mod = 1e6;

string half(string s) {
    string ret;
    int num = 0;

    for (auto c : s) {
        num *= 10;
        num += (c - '0');
        ret += to_string(num / 2);
        num %= 2;
    }
    if (ret.front() == '0') {
        ret.erase(0, 1);
    }

    return ret;
}

string s_down(string s) {
    string ret = s;
    for (int i = ret.length() - 1; i >= 0; i--) {
        int cur = ret[i] - '0' - 1;
        cur = (cur < 0) ? cur + 10 : cur;
        ret[i] = cur + '0';

        if (cur != 9) {
            break;
        }
    }

    if (ret.front() == '0') {
        ret.erase(0, 1);
    }

    return ret;
}

vector<long long> mat_mul(vector<long long> &a, vector<long long> &b) {
    vector<long long> ret(4);
    int idx = 0;

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ret[idx++] =
                ((a[i * 2] * b[j]) % mod + (a[i * 2 + 1] * b[j + 2]) % mod) %
                mod;
        }
    }

    return ret;
}

vector<long long> sol(string n) {
    if (n == "1") {
        return base;
    }

    if ((n.back() - '0') % 2) {
        n = s_down(n);
        vector<long long> tmp = sol(n);
        return mat_mul(tmp, base);
    } else {
        vector<long long> tmp = sol(half(n));
        return mat_mul(tmp, tmp);
    }
}

int main() {
    string s;
    cin >> s;

    long long ret;
    if (s == "0") {
        ret = 0;
    } else if (s == "1" || s == "2") {
        ret = 1;
    } else {
        string n = (s.back() % 2) ? half(s) : s_down(half(s));
        vector<long long> vec = sol(n);

        if (s.back() % 2) {
            ret = (vec[2] + vec[3]) % mod;
        } else {
            ret = (vec[0] + vec[1]) % mod;
        }
    }

    printf("%lld", ret);

    return 0;
}