import sys
input = sys.stdin.readline
mod = 1000000007
def multiply(A1,A2):
result = [[0,0],[0,0]]
for i in range(2):
for j in range(2):
for k in range(2):
result[i][j] += A1[i][k]*A2[k][j]
result[i][j] %= mod
return result
def cal(A,n):
if n == 1:
return A
cal2 = cal(A,n//2)
result = multiply(cal2,cal2)
if n%2:
return multiply(result,A)
return result
N = int(input())
if N%2:
print(0)
else:
N //= 2
A = [[4,-1],[1,0]]
print(sum(cal(A,N)[0])%mod)
#[0,0,3,0,11,0,41,0,153,0,571,0,2131,0,7953,0,29681,0,110771,0,413403,0,1542841,0,5757961,0,21489003,0,80198051,0,299303201]
엄청 쉽게 풀었는데, 증명은 못하겠는 문제
타일 채우기 1 문제 [백준 2133번] 타일 채우기 (Python3) (tistory.com) 에서 1~30까지의 값을 저장해놨었는데, 이걸 읽다보니까 점화식이 바로 보였다.
N이 짝수인 경우 n = N//2에 대해서 a[n] = 4*a[n-1] - a[n-2] 라는 것이다.
점화식이 바로 보였기 때문에 문제 푸는건 매우 수월했다.
피보나치 수 - 6에서 [백준 11444번] 피보나치 수 6 (Python3) (tistory.com) 당시에는 행렬 제곱으로 풀지는 않았지만 피보나치 수를 행렬로 바꿔서 푸는 방법을 배웠었는데, 이를 이용하면 아주 쉽게 풀 수 있다.
피보나치 수에서 점화식을 이용한 행렬이 [[1,1],[1,0]] 이었던 것처럼 이번 문제의 행렬은 [[4,-1],[1,0]]이 된다. 그리고 분할정복을 이용한 거듭제곱을 이용해서 풀면 된다.
그런데 문제는 저 점화식이 왜 성립하는지는 알 수가 없다는 것이다. 숫자를 나열하면 1초만에 보이지만 증명해보라고 하면 흠; 어려운 문제이다.
오늘의 교훈) 왜 저런 점화식이 성립하는지 고민해보자