8059 : 피보나치 수열
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 13
•통과: 1
•만든사람: suakii
문제 설명
피보나치 수열 $F_n$은 다음과 같이 정의됩니다:
- $F_0 = 0$
- $F_1 = 1$
- $F_n = F_{n-1} + F_{n-2}$ ($n \ge 2$)
정수 $n$이 주어질 때, $F_n \pmod{10^9+7}$을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $0 \le n \le 10^{18}$
- $F_0 = 0$
- $F_1 = 1$
- $F_n = F_{n-1} + F_{n-2}$ ($n \ge 2$)
정수 $n$이 주어질 때, $F_n \pmod{10^9+7}$을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $0 \le n \le 10^{18}$
입력 설명
첫째 줄에 정수 $n$이 주어집니다. ($0 \le n \le 10^{18}$)
출력 설명
$F_n \pmod{10^9+7}$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
55도움
$n$이 매우 크므로 일반적인 $O(n)$ 동적 계획법은 시간 초과가 발생합니다. 행렬 거듭제곱 기법 $\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$을 적용하여 분할 정복으로 행렬을 $O(\log n)$에 거듭제곱하여 빠르게 피보나치 수를 구합니다.