Neo Ground

11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 $n$번 째 피보나치 수를 $10^9+7$로 나눈 나머지를 구하여라. $n$은 $10^{18}$보다 작거나 같은 자연수이다. 아이디어 $n$이 매우 크다. 단순하게 기본적인 피보나치 재귀 함수를 구현해서는 불가능하다. 따라서 다음과 같이 생각해 보았다. 1. 일반항을 통해 구하기 -> 일반항에 $\sqrt 5$가 포함되어 계산이 간단하지 않다. 점화식에 포함된 제곱을 분할정복을 사용한다 하더라도 많은 제곱을 할 수록 부동소수점의 오차가 쌓일 것이다. -> 불가능 2. 점화식을 통한 분할정복을 통해 구하기 -> $f(2n)=g(f(n),..