문제

문제 링크 : https://www.acmicpc.net/problem/11444

풀이

보통 피보나치 수를 구할 땐 재귀나 DP를 이용해서 구하곤 한다.

하지만 이 문제의 경우 입력의 최댓값이 10^18 이기 때문에 재귀와 DP를 이용하면 시간 초과가 뜬다.

그래서 '분할 정복을 이용한 거듭제곱' 이라는 새로운 방법을 사용해야 한다.

분할 정복을 이용한 거듭제곱

A^8을 계산하는 방법을 생각해보자.

$A^8$은 A를 8번 곱한 것이므로 $A*A*A*A*A*A*A*A$ 와 같이 구할 수 있다. 따라서 총 8번의 계산을 해야한다.

하지만 지수법칙을 활용하면 계산량을 줄일 수 있다.
$A^8 = ((A^2)^2)^2$ 이므로 $A^2$을 구하는 연산, $(A^2)^2$을 구하는 연산, $((A^2)^2)^2$을 구하는 연산이 필요하다. 즉 3번의 계산을 해야한다. 처음의 방법과 비교하면 시간복잡도가 $O(N)$에서 $O(\log{N})$으로 줄어들었음을 알 수 있다.

따라서 n이 1이 될 때까지, n이 짝수일 때는 $A^n = A^{n/2} * A^{n/2}$, n이 홀수일 때는 $A^n = A^{(n - 1) / 2} * A^{(n - 1) / 2} * A$와 같이 나타내서 계산해주면 $O(\log{N})$의 시간 복잡도로 거듭제곱을 계산할 수 있다.

피보나치 수는 거듭제곱과 관련이 없어보이기 때문에 이 방법을 어떻게 적용해야할지 막막할 수 있다.

이때 사용하는 것이 행렬의 곱이다.

i번째 피보나치 수 $F_i$의 점화식은 다음과 같다.

이를 행렬로 나타내면 다음과 같다.

이처럼 피보나치 수를 행렬의 곱으로 나타낼 수 있으므로 분할 정복을 이용한 거듭제곱을 이용하여 행렬의 i 제곱을 구하면 i번째 피보나치 수도 $O(\log{n})$의 시간 복잡도로 구할 수 있다.

import sys
input = sys.stdin.readline
MOD = 1000000007

n = int(input())

def matrixMult(a,b):
    l = [[0,0],[0,0]]
    l[0][0] = a[0][0] * b[0][0] % MOD + a[0][1] * b[1][0] % MOD
    l[1][0] = a[1][0] * b[0][0] % MOD + a[1][1] * b[1][0] % MOD
    l[0][1] = a[0][0] * b[0][1] % MOD + a[0][1] * b[1][1] % MOD
    l[1][1] = a[1][0] * b[0][1] % MOD + a[1][1] * b[1][1] % MOD
    return l

def fib(n):
    if n == 1:
        return [[1,1],[1,0]]
    temp = fib(n // 2)
    if n % 2 == 1:
        return matrixMult(matrixMult(temp,temp),fib(1))
    else:
        return matrixMult(temp,temp)

print(fib(n)[1][0] % MOD)