링크: https://www.acmicpc.net/problem/13976 문제 2133번 문제와 같이 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이지만, N의 범위가 \(10^{18}\) 이다. 풀이 이전에 작성한 2133번 문제의 2번째 풀이 방법과 같지만 그것을 빠르게 계산해야한다. 피보나치 수를 빠르게 구하는 방법과 마찬가지로, 행렬을 이용한 거듭 제곱 트릭을 사용하면 된다. 수열의 값은 같으므로, 편의상 OEIS A001835 수열 \( f(n) = 4 \cdot f(n-1) - f(n-2) \) 을 사용하겠다. 이것을 행렬로 나타내면 아래와 같다. $$\begin{eqnarray} \left( \begin{array}{ccc} f_{n} \\ f_{n-1}..

링크: https://www.acmicpc.net/problem/2133 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 풀이 3×N 벽을 채우는 경우를 \(f(n)\), 한 칸이 빈 3×N 벽을 채우는 경우를 \(g(n)\) 라고 하자. 왼쪽부터 2×1 또는 1×2 크기의 타일을 하나씩 채워보면서 가능한 경우를 살펴본다. \(g(0)\)와 \(g(2)\)는 타일을 채울 방법이 없으므로 \(g(0) = g(2) = 0\) 이다. 이것을 식으로 나타내면 이렇다. $$f(n) = \begin{cases} 0 & \text{if $n$ < 2} \\ 2g(n-1) + f(n-2) \end{cases}$$ $$g(n) = \begin{cases} 1 & \text{i..