이번 문제는 피보나치 수 문제 중에서 입력값이 정말 크게 주어진 경우이다. 우선 내가 할 수 있는 최선의 피보나치 수 코드는 다이나믹 프로그래밍 알고리즘을 통한 작성이기 때문에 다이나믹 프로그래밍을 작성하였고 메모리 초과라는 결과를 얻었다.

n=int(input())
dp=[0 for _ in range(n+1)]
dp[1]=1
for i in range(2, n+1):
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[n]%1000000007)

그래서 찾아본 결과 피보나치 수열의 특성 중 다음과 같은 특성이 존재한다는 사실을 알게 되었다. 다음은 피보나치 수열을 행렬 형태로 나타낸 것이다.

이를 식으로 정리하면 다음과 같이 정리되었다.

즉, 행렬의 거듭제곱을 통해 피보나치 수를 구할 수 있다. 초기 행렬은

1 1
1 0

으로 두어야 한다. 이때의 n은 2가 되므로 결과적으로 작성한 함수에 들어가는 인자는 n-2로 들어가게 된다.

• n을 입력받는다.
• p을 1,000,000,007로 선언한다.
• power함수를 adj, n을 인자로 갖도록 선언한다.
  -> 만약 n이 1일 경우, adj를 반환한다.
  -> 만약 n이 짝수일 경우,
  --> multi(power(adj, n-1), adj)를 호출한다.
  -> 그 외의 경우,
  --> power(multi(adj, adj), n//2)를 호출한다.
• multi함수를 a, b를 인자로 갖도록 선언한다.
  -> 임시 리스트 tmp를 2*b[0]의 길이의 크기로 선언하고 0으로 채운다.
  -> 2번 반복하는 i에 대한 for문을 돌린다.
  --> b[0]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
  ---> total을 0으로 선언한다.
  ---> 2번 반복하는 k에 대한 for문을 돌린다.
  ----> total에 a[i][k]*b[k][j]를 더한다.
  ---> tmp[i][j]를 total%p로 갱신한다.
  -> tmp를 반환한다.
• 초기 행렬 adj를 [[1, 1], [1, 0]]으로 선언한다.
• start를 [[1], [1]]로 선언한다.
• 만약 n이 3보다 작을 경우, 1을 출력한다.
• 그 외의 경우, multi(power(adj, n-2), start)[0][0]을 출력한다.

Code

n=int(input())
p=1000000007
def power(adj, n):
    if n==1:
        return adj
    elif n%2:
        return multi(power(adj, n-1), adj)
    else:
        return power(multi(adj, adj), n//2)
def multi(a, b):
    tmp=[[0]*len(b[0]) for _ in range(2)]
    for i in range(2):
        for j in range(len(b[0])):
            total=0
            for k in range(2):
                total+=a[i][k]*b[k][j]
            tmp[i][j]=total%p
    return tmp
adj=[[1, 1], [1, 0]]
start=[[1], [1]]
if n<3:
    print(1)
else:
    print(multi(power(adj, n-2), start)[0][0])