11444 피보나치 수 6

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

F[2n-1] = F[n]^2+F[n-1]^2

F[2n] = (F[n-1]+F[n+1])*F[n] = (2*F[n-1]+F[n])*F[n]

위의 두 점화식을 이용하여 메모이제이션을 한다.

#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
 
map<ll,ll> d;
ll mod=1000000007;
 
ll f(ll n)
{
    if(n<=0) return 0;
    else if(n==1 || n==2) return 1;
    else if(d.count(n)>0) return d[n];
 
    if(n%2)
    {
        ll m=(n+1)/2,a=f(m),b=f(m-1);
        d[n]=(a*a+b*b)%mod;
        return d[n];
    }
    else
    {
        ll m=n/2,a=f(m-1),b=f(m);
        d[n]=((2*a+b)*b)%mod;
        return d[n];
    }
}
 
int main()
{
    ll n;
    scanf("%lld",&n);
    printf("%lld",f(n));
    return 0;
}