[BOJ] 피보나치 수의 제곱의 합

피보나치 수의 제곱의 합

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 ≤ N ≤ 1,000,000,000,000,000,000)	도가뉴 항등식, Math

간단한 문제 증명은 여기에서 확인하시면 됩니다.

도가뉴 항등식을 활용해서 큰 피보나치 구하면 되구요. 이제 제곱의 합을 어떻게 구할까?를 생각해보면 됩니다.

제 의식은 흐름은 아래와 같습니다: first last

정답 코드


#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
using namespace std;
using ll = long long;
ll MOD = 1'000'000'007;

map<ll, ll> dp;



ll solution(ll n){
    if(dp.find(n) != dp.end()) return dp[n];
    ll result;
    
    ll a, b;
    a = solution(n/2);
    b = solution(n/2+1+(-2 *!(n%2)));
    
    if(n%2) result = ((a * a)%MOD + (b * b)%MOD)%MOD;
    else result = ((((2*b)%MOD + a)%MOD)*a)%MOD;
    dp[n] = result;
    
    return result;
}




int main() {
    ll n;
    cin >> n;
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    
    ll a = solution(n);
    ll b = solution(n+1);
    
    // 이게 F_n*F_(n+1)이여서
    
    
    cout << ((a * b) % MOD);
    

    return 0;
}