파이썬) 백준 알고리즘 | 11440번 : 피보나치 수의 제곱의 합

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

11440번: 피보나치 수의 제곱의 합

풀이

$$ F_{k+1} = F_k + F_{k-1} $$

$$ F_k = F_{k+1} - F_{k-1} $$

$$ F_{k} ^ {2} = F_kF_{k+1} - F_{k-1}F_k  $$

$$ F_{1} ^ {2} = 1 = F_1F_2 - F_0F_1  $$

$$ F_{2} ^ {2} = F_2F_3 - F_1F_2  $$

$$ F_{3} ^ {2} = F_3F_4 - F_2F_3  $$

$$ F_{4} ^ {2} = F_4F_5 - F_3F_4  $$

$$ F_{n} ^ {2} = F_nF_{n+1} - F_{n-1}F_n  $$

$$ \therefore  \sum_{k=1}^n F_{k} ^ {2} = F_nF_{n+1}  $$

이렇게 유도할 수 있습니다.

 

그리고 나머지 곱 분배법칙은

(x * y) % m = ((x % m) * (y % m)) % m 이라고 합니다.

 

그리고 마지막으로 n이 1,000,000,000,000,000,000보다 작거나 같은 수에서는

피보나치 수를 구하는 속도가 굉장히 빨라야 하므로$$ f(n) = f(a)f(n-a+1) + f(a-1)f(n-a)  $$식을 유도해서 사용했습니다.그래서 딕셔너리를 이용한 재귀함수에서 n이 100보다 크면 이 공식으로 구하도록 구현하였습니다.

n = int(input())
dic = {}
m = 1000000007
def fibo(n):
    a = n // 3
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        if not n in dic.keys():
            if n > 100:
                dic[n] = (fibo(a) * fibo(n-a+1) + fibo(a-1) * fibo(n-a)) % m
            else:
                dic[n] = (fibo(n-1) + fibo(n-2)) % m
    return dic[n]
print((fibo(n) % m) * (fibo(n+1) % m) % m)