13976 타일 채우기 2

A. 문제 요약

$3 \times N$의 공간을 $1 \times 2$ or $2 \times 1$ 타일로 채우는 방법의 갯수를 구하는 문제

B. 제한 조건

제한 시간 : 8초 (for python 3)
제한 메모리 : 1056 MB (for python 3)

C. 주의사항

1. 타일로 공간을 채울 적에 빈 칸이 존재하면 안 됨
   => $N$이 홀수일 경우 무조건 빈 칸이 존재하므로, 타일을 채울 방법이 없음.
2. 타일로 공간을 채울 적에 타일이 겹치면 안 됨
3. $N$의 제한 조건이 1,000,000,000,000,000,000임에 주의

D. How to Approach

1. 이 문제의 경우 $N$의 제한 조건이 매우 크므로, iteration을 통해서는 구할 수 없음.
2. 또한 방법의 갯수를 1,000,000,007로 나눈 갯수를 구하면 되므로, 점화식을 구한 뒤 행렬을 세팅해 분할 정복을 통한 거듭제곱으로 푸는 것이 적절해보임.

① 점화식 구하기

1. $N$이 짝수인 경우에 대해서만 생각하기 위해 $n=N/2$번째 항에 대해서 생각하기로 하자. 이 경우의 수를 $A(n)$이라 하면,
   1) 2칸을 제외하고 $2(n-1)$칸을 채우는 경우가 $3A(n-1)$이 존재한다.
   
   2) 4칸을 제외하고 $2(n-2)$칸을 채우는 경우가 $2A(n-2)$이 존재한다.
   
   3) 6칸을 제외하고 $2(n-3)$칸을 채우는 경우가 $2A(n-3)$이 존재한다.
   ...
   n-1) $2(n-1)$칸을 제외하고 2칸을 채우는 경우가 $2A(1)$이 존재한다.
   이를 다 더하면 $A(n)$이 나오게 된다. $A(1)$부터 $A(n)$까지의 합을 $S(n)$이라 하면,
   $A(n) = 3A(n-1) + 2S(n-2)$ (단, $n > 2$) ... (A-1)
   $A(n+2) = 3A(n+1) + 2S(n)$ ... (A-2)
   여기에 A(n)만의 식으로 나타내기 위해 $A(n+1) = 3A(n) + 2S(n-1)$을 변변 빼주면,
   $A(n+2) - A(n+1) = 3(A(n+1) - A(n)) + 2A(n)$ ... (A-3)
   $A(n+2) = 4A(n+1) - A(n)$ ... (A-4)
   이 최종 점화식이 된다.

② 분할 정복을 통한 거듭제곱을 위한 행렬 세팅

n의 제한이 $5 \times {10}^{17}$이므로, 이 점화식으로 다이나믹 프로그래밍을 사용하기엔 시간 제한적으로 무리가 상당히 따른다. 따라서, 분할 정복을 통한 빠른 거듭제곱을 위해 점화식을 바탕으로 한 행렬을 세팅하자.

$\begin{bmatrix}A(n+2)\\A(n+1)\\ \end{bmatrix}$ = $\begin{bmatrix}4&-1\\1&0\\ \end{bmatrix}$$\begin{bmatrix}A(1)\\A(0)\\ \end{bmatrix}$ ... (A-5)

으로 세팅을 하게 되면,

$\begin{bmatrix}A(n+2)\\A(n+1)\\ \end{bmatrix}$ = $\begin{bmatrix}4&-1\\1&0\\ \end{bmatrix}^{n+1}$ $\begin{bmatrix}A(1)\\A(0)\\ \end{bmatrix}$ ... (A-6)

이 되게 된다.

이 때, A(1) = 3, A(0) = 1로 설정을 하자. (because A(2) = 11)
$\begin{bmatrix}A(n+1)\\A(n)\\ \end{bmatrix}$ = $\begin{bmatrix}4&-1\\1&0\\ \end{bmatrix}^{n}$ $\begin{bmatrix}3\\1\\ \end{bmatrix}$ ... (A-8)
가 된다.

python의 경우 numpy를 통해 행렬의 곱셈을 간단하게 할 수 있지만, 이 상황의 경우 numpy를 사용할 수 없으므로, 행렬의 곱셈을 정의해주어야한다.

이를 하고 나면, 행렬을 $2^t$제곱한 리스트를 만들고, n을 이진수로 바꿔준 다음, 자릿수가 1인 부분에 해당하는 행렬($A^{2^t}$)을 곱해주면 원하는 값이 나오게 된다. 이때, 점화식대로 행렬을 곱하다 원소가 음수가 될 수도 있으니, % 연산을 쓰기 전에 따로 처리를 해준다.

E. 최종 코드

1. 행렬의 곱셈을 정의 후, 행렬의 거듭제곱 또한 함께 정의해준다.
2. N이 홀수인 경우 0을 print하고 빠져나오고, N이 짝수인 경우 N을 2로 나눈 후 분할 정복을 통한 거듭제곱을 한다

# 13976 타일 채우기 2

N = int(input())
mod = 1000000007
# 2*2 행렬 곱셈 정의
def matrix_multiply(
    matrix1: list[list[int]], matrix2: list[list[int]]
) -> list[list[int]]:
    new_matrix = [[0 for i in range(2)] for i in range(2)]
    for i in range(2):
        for j in range(2):
            new_matrix_element = 0
            for k in range(2):
                new_matrix_element += matrix1[i][k] * matrix2[k][j]
            if new_matrix_element >= 0:
                new_matrix[i][j] = new_matrix_element % mod
            else:
                new_matrix[i][j] = -1 * ((-1 * new_matrix_element) % mod)
    return new_matrix


# 2*2 행렬 제곱 정의
def matrix_square(matrix: list[list[int]]) -> list[list[int]]:
    return matrix_multiply(matrix, matrix)


if N % 2:
    print(0)
else:
    N //= 2
    # a(0) = 1, S(1) = 3
    # a(n+2) = 3*a(n+1)+2*S(n)
    # a(n+2) = 4*a(n+1)-a(n)
    matrix = [[4, -1], [1, 0]]
    # A**(2**n)에 대한 행렬을 세팅해두기
    matrix_powered_dict = dict()
    matrix_powered_dict[0] = matrix
    initial_matrix = [3, 1]
    for i in range(64):
        matrix_powered_dict[i + 1] = matrix_square(matrix_powered_dict[i])
    binary_index = [N // (2**i) % 2 for i in range(64)]
    # 2*2 단위 행렬 세팅
    final_matrix = [[1 if i == j else 0 for i in range(2)] for j in range(2)]
    # binary_index의 원소 중 1인 것들만 곱하기
    for k, j in enumerate(binary_index):
        if j:
            final_matrix = matrix_multiply(final_matrix, matrix_powered_dict[k])
    # 마지막으로 [3, 1] 곱하기
    final_value_list = [0, 0]
    for k in range(2):
        for j in range(2):
            final_value_list[j] += final_matrix[j][k] * initial_matrix[k]
    result = final_value_list[1] % mod
    print(result)