[백준 11440번] 피보나치 수의 제곱의 합 (Python3)

mod = 1000000007

def cal(A,n):
  if n==1:
    return A
  cal2 = cal(A,n//2)
  if n%2:
    return multiply(multiply(cal2,cal2),A)
  return multiply(cal2,cal2)

def multiply(A,B):
  result = [[0]*3 for i in range(3)]
  for i in range(3):
    for j in range(3):
      for k in range(3):
        result[i][j] += A[i][k]*B[k][j]%mod
      result[i][j] %=mod
  return result

N = int(input())
if N == 1:
  print(1)
else:
  matrix = [[2,2,-1],[1,0,0],[0,1,0]]
  matrix = cal(matrix,N-1)  
  print(matrix[0][0])

타일 채우기 2 [백준 13976번] 타일 채우기 2 (Python3) (tistory.com) 문제처럼 점화식을 찾아서 문제를 해결하였다. 그런데 타일 채우기 2 문제처럼 왜 저런 점화식이 성립하는지는 증명하지는 못하였다.

 

일단 피보나치 수의 제곱의 합은 0 1 2 6 15 40 104 273 ... 이다.

이때 이 수를 잘 조합해보면 An = (An-1+An-2)*2-An-3 가 성립한다는 것을 알 수 있다. 6 = (2+1)*2-0, 15 = (6+2)*2-1 ...

 

따라서 분할정복을 이용한 행렬의 거듭제곱으로 풀어줄 수 있었다.

 

 

오늘의 교훈) 왜 저런 점화식이 성립하는지 고민해보자