이 문제는 PKU의 3420 "Quad Tiling"을 풀고 나서 생각나서 만들어본 문제 입니다.
E번 Tiling문제는 보나마나 뻔한 DP 입니다. T[n]이 3xn 그리드를 채우는 방법의 가지수 라 하면
T[n] = aT[n-1] + bT[n-2] + cT[n-3] + dT[n-4] + .... 이런 형태로 식이 T[0]까지 전개됩니다 (T[0] = 1 이라 놓고요).
여기서 각 상수 a,b,c,d 등이 의미하는 바는:
a: 1xn 그리드를 수직으로 분할되지 않게 채우는 가지 수 ( =1)
b: 2xn 그리드를 수직으로 분할되지 않게 채우는 가지 수 ( =2)
c: 3xn 그리드를 수직으로 분할되지 않게 채우는 가지 수 ( =5)
이런식으로 계속 구해나갈 수 있습니다.
재미있는 점은 이 상수들이 반복된다는 것입니다.
상수만 적어보면, 적절히 큰 n에 대해 T[n]은 (1, 2, 5, 2, 2, 4, 2, 2, 4, ....) 이런식으로 '2, 2, 4'라는 상수들이 반복됩니다.
하지만 T[n]을 구하려면 T[0]~T[n-1]을 모두 구해야 한다는 단점이 있고, 시간복잡도가 O(n^2)이 되어서 문제를 풀 수 없게 됩니다.
그래서 식을 약간 고치면 (아마 고딩때 power series인가 할 때 이런걸 했던걸로 기억하는데...)
(1) T[n] = T[n-1] + 2T[n-2] + 5T[n-3] + 2T[n-4] + 2T[n-5] + 4T[n-6] + ...
(2) T[n+3] = T[n+2] + 2T[n+1] + 5T[n] + 2T[n-1] + 2T[n-2] + 4T[n-3] + 2T[n-4] + 2T[n-5] + 4T[n-6] ...
(2) - (1)을 하면:
T[n+3]-T[n] = (T[n+2] + 2T[n+1] + 5T[n] + 2T[n-1] + 2T[n-2] + 4T[n-3]) - (T[n-1] + 2T[n-2] + 5T[n-3)
이런식으로 T[n-4]이하 term들이 모두 소거됩니다 (반복 주기=3을 이용).
왼쪽변 T[n]을 오른쪽으로 옮기고, T[n+3]도 T[n]으로 고쳐주면 식이 정리되서 나옵니다.
T[n+3] = T[n+2] + 2T[n+1] + 6T[n] + T[n-1] -T[n-3]
정리해서 T[n] = T[n-1] + 2T[n-2] + 6T[n-3] + T[n-4] -Tn-6
이제 주어진 n이 10^9로 상당히 크므로, 고전적인 matrix multiplication을 이용해서 풀면 되겠습니다.
"아니 이게 뭔 소리야, DP인데 matrix가 왜 나와" 싶으신 분들은 PKU 3070번 문제를 tutorial 삼아 풀어보시면 되겠습니다.
쉽게 말해, DP식이 "T[n] = 상수 개의 낮은 term" 들로 표현되는 경우, matrix 식으로 변환하여 풀 수 있습니다.
이 문제 맨 처음에 언급했던 식은 상수 개의 term들이 아니고 n개의 term이었죠 (T[n-1] .. .T[0]). 이러면 matrix로 바꿀 수가 없습니다. 그래서 식을 적절히 정리해서 어떤 n이든 상수개의 term이 나오게 하면 됩니다.
자, 다음은 test case가 3만개 정도 까지 들어온다고 나왔었는데요 (실제로는 21010개만 넣었습니다), 시간복잡도를 대충 계산해봅시다.
최악의 경우 행렬 곱을 2*(log n) 번 정도 해야하니까 약 60번, 한 번 하는데 6^3 = 약 216, test case는 3만개. 약간... 느리죠.
행렬 곱을 미리 pre-compute해서, A^0, A^1, A^2, ..., A²⁹ 까지 미리 구해놓으면 시간을 많이 절약할 수 있습니다 (같은 작업을 계속 하니까요).
여기까지는 '모법 답안' 이었습니다.
제가 이 문제를 낸 이유는 '2등 답안' 때문입니다. 위에선 6x6 matrix로 변환해서 풀었는데, 이 문제는 (2^6)x(2^6) matrix로도 풀 수 있습니다.
물론 matrix가 아주 크기 때문에 제가 설정한 제한에서는 TLE가 납니다. 그래도 한 번 읽어볼 가치는 있는 방법입니다.
2^6이 왜 나왔냐..하면은, 가장 오른쪽 2열의 '상태'를 표현한 것이라고 보면 되겠습니다.
이제 T[n, s]를 정의하는데: T[n, s] = 3xn 그리드를 적절히 채워서 1~n-2열은 모두 꽉 차고, 마지막 2 열의 상태가 's'인 경우의 가지 수.
s= 0 이면 두 열이 모두 빈 것이고, s = 2^6-1 이면 두 열이 모두 꽉 찼다고 합시다.
편의를 위해 아래와 같이 정의하면 좋습니다:
2^0 2^3
2^1 2^4
2^2 2^5
(n-1) (n) 행
우리가 구하려는 답은 T[n, 2^6-1]에 저장되어 있겠구요 (3xn 그리드를 모두 꽉 채우는 방법의 가지수).
여기서 T[n, s]는 T[n-1, *]에만 depend 합니다. 그래서 T[n, s] 은 T[n-1, 0] ~ T[n-1, 2^6 -1]에 대한 식으로 나오게 됩니다 (term이 2^6 = 64개 ㅎㄷㄷ); 물론 대부분의 coefficient는 0이 되구요.
이 경우, 손으로 일일이 세지 않고 프로그램이 세개 하는 방법을 사용하여 (2^6) x (2^6) matrix를 찾을 수 있습니다.
매트릭스를 구하고 나면, 위에서 한 방법대로 문제를 풀면 되구요.
이 풀이는 물론 비효율적이지만, '문제에 따라서는' 맨 처음 설명했던 방법보다 좋을 수도 있습니다. 맨 처음 방법의 단점이라면, '내가 까먹고 경우의 수를 잘못 센 경우'에 망할 수 있으나, 두 번째 방법은 직접 세지 않고 모든 경우를 프로그램이 세기 때문에 코딩에서 실수한 것이 아니라면 좋은 방법이 될 수 있습니다.
앞서 언급한 QuadTiling도 저는 4x4 matrix를 찾아서 풀었는데, 학교에서 연습할 때 (2^4)x(2^4) 로 푸는 아이가 있어서 '아니 이게 뭥미' 싶어서 토론을 하다가 알게됐습니다. 혹시 counting을 하기 어려운 문제가 나오면, 이런식으로 약간의 brute force로 간단히 답을 찾아서 해보는 것도 나쁘지 않다 싶네요.
솔루션이 나중에 공개된다면 blocks_fast.cpp 는 모법 답안, blocks_slow.cpp는 2등 답안 입니다. 참고하세요.