import sys
input = sys.stdin.readline
memory = {1:1,2:1,3:2,4:3,5:5}
def Fibo(n):
if memory.get(n):
return memory[n]
else:
if n%2 == 1:
memory[n] = (Fibo(n//2)**2+Fibo(n//2+1)**2)%1000000000
else:
memory[n] = (Fibo(n+1)-Fibo(n-1))%1000000000
return memory[n]
a,b = map(int,input().split())
print((Fibo(b+2)-Fibo(a+1))%1000000000)
일단 풀이는 매우 쉽다. 피보나치 수열의 합을 쭉 나열해보면 0 1 2 4 7 12 20 33 54 88 ... 이 나오는데, 이를 피보나치 수열인 0 1 1 2 3 5 8 13 21 34 와 비교해보면 피보나치 수열의 n까지의 합은 n-2번째 피보나치 수에서 1을 빼준 수와 같다는 규칙성이 보이게 된다.
따라서 [백준 11444번] 피보나치 수 6 (Python3) (tistory.com) 의 코드를 그대로 이용해서 풀 수 있었다.
다만 어떻게 증명하느냐가 문제인데, 이는 시그마 공식을 이용하면 유도할 수 있다.
Sn = an+an-1+...+a0
Sn-1 = an-1+an-2+...+a0
Sn-2 = an-2+an-3+...+a0
이를 정리해보면 Sn, Sn-1, Sn-2 사이에 Sn = Sn-1+ Sn-2 + 1이라는 규칙이 성립한다는 것을 알 수 있다.
피보나치 수의 성질에 대해서 알려주는 좋은 문제였다.
오늘의 교훈) 피보나치 수는 재미있다.