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 ...
따라서 분할정복을 이용한 행렬의 거듭제곱으로 풀어줄 수 있었다.
오늘의 교훈) 왜 저런 점화식이 성립하는지 고민해보자