문제
3×n 크기의 직사각형을 1×2 또는 2×1 도미노로 채우는 방법의 수를 구한다. 결과는 1,000,000,007로 나눈 나머지를 출력한다. n은 최대 10^18까지 가능하다.
입력
- 첫째 줄: 정수 n (1 ≤ n ≤ 10^18)
출력
3×n 직사각형을 채우는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 | 3 |
4 | 11 |
풀이
n이 홀수이면 3×n은 짝수 개의 칸을 가질 수 없으므로 답은 0이다. n이 짝수일 때 d[n] = 4*d[n-2] - d[n-4] 점화식이 성립한다. n이 최대 10^18이므로 일반 DP로는 불가능하고, 이 점화식을 2×2 행렬로 표현한 뒤 행렬 거듭제곱을 분할 정복으로 O(log n) 계산한다.
- n이 홀수이면 0을 출력하고 종료한다.
- n이 2이면 3을 출력한다.
- n이 4 이상 짝수이면 점화식
d[n] = 4*d[n-2] - d[n-4]을 행렬식으로 변환한다. - 전이 행렬
[[4,-1],[1,0]]의(n/2 - 1)제곱을 분할 정복으로 계산한다. - 결과 행렬에 초기 벡터
[d[2], d[0]] = [3, 1]을 곱해d[n]을 구한다. - 음수 방지를 위해 나머지 연산 시 MOD를 더한 후 취한다.
핵심 아이디어: 점화식 d[n] = 4*d[n-2] - d[n-4]은 2133 문제의 점화식 d[n] = 3*d[n-2] + 2*(d[n-4] + ... + d[0])을 수학적으로 정리한 것이다. n이 최대 10^18이므로 선형 DP로는 시간 초과이며, 행렬 거듭제곱의 분할 정복을 통해 O(log n) 시간으로 해결한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day90BOJ13976행렬곱분할정복DP타일채우기2 { // 13976 타일 채우기 2 이지만, 분할정복이 더 중요한 문제
static final long MOD = 1_000_000_007;
static long N, ans; // 구선생님 도움 long타입의 배열은 못만듬
static long[] bc = { 3, 1 }; // d[2] , d[0]
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Long.parseLong(br.readLine());
if (N % 2 != 0)
ans = 0L;
else if (N == 2)
ans = 3L;
else {
ans = mul(pow(new long[][] { { 4, -1 }, { 1, 0 } }, N / 2 - 1), bc);
}
System.out.println(ans);
br.close();
}
private static long[][] pow(long[][] matrix, long n) {
if (n == 1)
return matrix;
else if (n % 2 == 0) {
long[][] tmp = pow(matrix, n / 2);
return mul(tmp, tmp);
} else
return mul(pow(matrix, n - 1), matrix);
}
private static long[][] mul(long[][] a, long[][] b) { // MultiMatrix 2x2 * 2x2
long[][] tmp = new long[2][2];
tmp[0][0] = get(a[0][0], b[0][0], a[0][1], b[1][0]);
tmp[0][1] = get(a[0][0], b[0][1], a[0][1], b[1][1]);
tmp[1][0] = get(a[1][0], b[0][0], a[1][1], b[1][0]);
tmp[1][1] = get(a[1][0], b[0][1], a[1][1], b[1][1]);
return tmp;
}
// (1 2) - (a[0][0]*b[0][0]+a[0][1]*b[1][0] a[0][0]*b[0][1]+a[0][1]*b[1][1])
// (3 4) - (a[1][0]*b[0][0]+a[1][1]*b[1][0] a[1][0]*b[0][1]+a[1][1]+b[1][1])
private static long mul(long[][] a, long[] b) { // MultiMatrix 2x2 * 2x1
return get(a[0][0], b[0], a[0][1], b[1]);
}
// 원래 식은 long[]으로 반환되며,
// (d[ n ]) = a[0][0]*b[0] + a[0][1]*b[1]
// (d[n-2]) = a[1][0]*b[0] + a[1][1]*b[1] 이지만, d[n]만 반환
private static long get(long a, long b, long c, long d) { // 행렬 곱 + 음수 처리 + MOD
return ((a * b % MOD) + (c * d % MOD) + MOD) % MOD;
}
// 원래 식은 a * b + c * d 인데 행렬에 -1값 때문에 음수가 나올 수 있어
// MOD를 더해서 나머지를 유지한다.
}
// 2133 문제의 점화식은 dp[n] = dp[n-2]*3 + 2(dp[n-4] ~ dp[n-n])
// d[4] = 3*d[2] + 2*d[0]
// d[6] = 3*d[4] + 2*d[2] + 2*d[0]
// ---- = 3*d[4] + 2*d[2] + 2*d[0] + d[2] - d[2]
// ---- = 3*d[4] + 3*d[2] + 2*d[0] - d[2]
// ---- = 3*d[4] + d[4] - d[2]
// ---- = 4*d[4] - d[2] (4*d[n-2] - d[n-4])
// d[8] = 3*d[6] + 2*d[4] + 2*d[2] + 2*d[0]
// ---- = 3*d[6] + 2*d[4] + 2*d[2] + 2*d[0] + d[4] - d[4]
// ---- = 3*d[6] + 3*d[4] + 2*d[2] + 2*d[0] - d[4]
// ---- = 3*d[6] + d[6] - d[4]
// ---- = 4*d[6] - d[4]
// d[n] = 4d[n-2] - d[n-4] <<-- 최종식
// 행렬식
// d[4] = 4*d[2] - d[0]
// d[2] = d[2] 0
// (d[4]) - (4 -1)(d[2])
// (d[2]) - (1 _0)(d[0]) //행렬식...
// ----
// (d[6]) - (4 -1)^2(d[2])
// (d[4]) - (1 _0)__(d[0])
// ----
// (d[8]) - (4 -1)^3(d[2])
// (d[6]) - (1 _0)__(d[0])
// ----
// (d[10]) - (4 -1)^4(d[2])
// (_d[8]) - (1 _0)__(d[0])
// ----
// (d[ n ]) - (4 -1)^((n/2)-1)(d[2])
// (d[n-2]) - (1 _0)__________(d[0]) // 지수형 행렬식 -> 거듭제곱의 분할정복
// ----
// 행렬의 곱
// (a b)(i j) -\ (a * i + b * k a * j + b * l)
// (c d)(k l) -/ (c * i + d * k c * j + d * l)
// (a b)( i ) -\ (a * i + b * j)
// (c d)( j ) -/ (c * i + d * j)
// (___)( | )
// (___)( | ) 가로 세로 곱이라고 하면 기억이 나려나...복잡도
- 시간: O(log N) — 2×2 행렬 거듭제곱의 분할 정복
- 공간: O(log N) — 분할 정복 재귀 스택 깊이