백준 1788번

#include <iostream>
#include <string>
#define max_num 1000000000
long long f_arr[1000001] = {0,1,};
bool chk[1000001] = {1,1,0,};

void fibonacci(int n){
    if (chk[n] == 0) {
        f_arr[n] = (f_arr[n-1] + f_arr[n - 2]) % max_num;
        chk[n] = 1;
    }
}

int main() {
    long long n,res = 0;
    int sign = 0;
    std::cin >> n;
    if (n < 0) {
        for (int i = 0; i <= (-n); i++) {
            fibonacci(i);
        }

    }
    else{
        for (int i = 0; i <= n; i++) {
            fibonacci(i);
        }
    }

    if (n > 0)
        sign = 1;
    else if (n == 0)
        sign = 0;
    else{
        if(n%2==0)
            sign = -1;
        else
            sign = 1;
    }

    if (n < 0)
        res = f_arr[-n];
    else
        res = f_arr[n];


    std::cout << sign << std::endl << res;
    return 0;

}