BOJ 13976 - 타일 채우기 2

링크: 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} \end{array} \right) & = & \left( \begin{array}{ccc} 4 \cdot f_{n-1} - f_{n-2} \\ f_{n-1} \end{array} \right) \\ & = & \begin{pmatrix} 4 & -1 \\ 1 & 0 \end{pmatrix}  \left( \begin{array}{ccc} f_{n-1} \\ f_{n-2} \end{array} \right) \end{eqnarray}$$

 

이렇게 중간에 4x4 행렬 ((4, -1), (1, 0)) 을 얻었고, 초기 항에 이것을 $n$번 제곱하면 $f(n)$을 구할 수 있다.

$$\left( \begin{array}{ccc} f_{n} \\ f_{n-1} \end{array} \right) = {\begin{pmatrix} 4 & -1 \\ 1 & 0 \end{pmatrix}}^{n} \left( \begin{array}{ccc} f_{2} \\ f_{1} \end{array} \right) = {\begin{pmatrix} 4 & -1 \\ 1 & 0 \end{pmatrix}}^{n} \left( \begin{array}{ccc} 3 \\ 1 \end{array} \right)$$

 

거듭 제곱을 빠르게 하는 트릭은 $a^{4} = a^{2} \cdot a^{2}$ 을 이용해서, 한번 계산한 $a^{2}$를 재사용하는 방법이다. 이것을 행렬에도 그대로 적용할 수 있다.

 

코드

주의할 점은, 행렬 중간에 음수가 있을 수 있으니 모듈러를 통해 양수로 적절히 변환해줘야한다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long lld;
	const lld MOD = 1e9 + 7;
	const int INF = 0x3f3f3f3f;
	const lld LNF = 0x3f3f3f3f3f3f3f3f;
	struct mat4 {
	lld a, b, c, d;
	mat4() {
	a = 1, b = 0, c = 1, d = 0;
	}
	mat4(lld a, lld b, lld c, lld d) {
	this->a = a;
	this->b = b;
	this->c = c;
	this->d = d;
	}
	mat4 operator * (const mat4& m) {
	return mat4(
	((a * m.a) % MOD + (b * m.c) % MOD) % MOD,
	((a * m.b) % MOD + (b * m.d) % MOD) % MOD,
	((c * m.a) % MOD + (d * m.c) % MOD) % MOD,
	((c * m.b) % MOD + (d * m.d) % MOD) % MOD
	);
	}
	mat4 pow(lld n) {
	if (n == 0) return mat4();
	if (n == 1) return *this;
	mat4 h = pow(n / 2), m = h * h;
	if (n & 1) return m * (*this);
	return m;
	}
	};
	lld solution(lld n) {
	if (n & 1) return 0;
	mat4 m(4, -1, 1, 0);
	lld ans = (m.pow(n / 2 - 1) * mat4(3, 0, 1, 0)).a;
	return (ans + MOD) % MOD;
	}
	int main() {
	lld n;
	scanf("%lld", &n);
	printf("%lld\n", solution(n));
	return 0;
	}

view raw boj-13976.cpp hosted with ❤ by GitHub