타일 채우기 2

문제 링크

발상

문제를 보자마자 알 수 있다. 입력 크기 제한이 좀 이상하다. 입력 크기로 미루어보아 이 문제는 $O(\log n)$이하의 알고리즘으로만 해결할 수 있다. 우선 타일을 채우는 경우의 수로 점화식부터 유추해보자. 주어진 타일 크기가 2칸짜리 밖에 없으므로 N이 홀수인 경우는 경우의 수가 0이고 짝수인 경우만 살펴보자. 다음과 같이 진행된다.

N = 0, 2, 4, 6 ( 0, 1, 2, 3 )
D = 1, 3, 11, 41

그리고 예시 입출력에 $N$이 $100$일 때 답이 $436252889$ 라고 알려줬다. 이런 패턴 맞추기 문제는 솔직히 직접 패턴 조합해보면서 점화식을 찾을 수 밖에 없다. 정말 순수 노가다라고 할 수 있다. 난 타일 맞추기류가 정말 싫다. 그나마 큰 $N$의 답을 알려줬으니 유추한 점화식의 정답 여부를 확인할 수 있다. 이제 점화식을 한번 찾아보자. 가장 기본이 되는 단위인 $N=2$의 케이스부터 살펴보면 아래와 같이 3가지 패턴이 있다.

그리고 4, 6, 8 .. 식으로 $N$이 증가할 때마다 다음과 같이 패턴이 증가한다.

따라서 점화식의 형태는 $N_i=N_{i-1}\times 3+\alpha$ 가 될 것이다. 저 $\alpha$는 경계를 합친 아래와 같은 조합들을 의미한다.

저 경계를 합친 조합은 $N=4$일 때 $2$개로 시작해 각 단계마다 새로운 조합 2개가 추가된다. 즉, $\alpha$는 아래와 같이 나타낼 수 있다. 편의상 $N$이 홀수인 경우는 제외하고 짝수인 경우만 2로 나눠 풀이를 작성했다.

$$\alpha =2\sum _{k=0\to i-2}{N}_k$$

즉 점화식은 아래와 같다.

$$N_i=3N_{i-1}+2\sum _{k=0\to i-2}{N}_k$$

문제는 이 점화식은 시그마를 포함하고 있어 점화식 계산 자체가 $O(N^2)$다. 따라서 시그마를 제거하기 위해 다음과 같이 식을 변형해야 한다. 수학에서 일차방정식 가감법을 떠올리면 된다.

$$\begin{array}{rlr}{N}_i& =3N_{i-1}+2\sum _{k=0\to i-2}{N}_k& \\ N_i& =3N_{i-1}+2\times (N_{i-2}+N_{i-3}+...+N_0)& \text{... (1)}\\ & & \\ N_{i-1}& =3N_{i-2}+2\sum _{k=0\to i-3}{N}_k& \\ N_{i-1}& =3N_{i-2}+2\times (N_{i-3}+N_{i-4}+...+N_0)& \text{... (2)}\\ & & \\ \text{(1)}-\text{(2)}& =& \\ N_i-N_{i-1}& =3N_{i-1}-N_{i-2}& \\ N_i& =4N_{i-1}-N_{i-2}& \end{array}$$

이렇게 가감법을 활용해 시그마를 제거할 수 있다.

최종 점화식 $N_i=4N_{i-1}-N_{i-2}$ 을 얻었다. 자, 그럼 이제 동적 계획법 가장 처음에 배웠던 것 처럼 $O(N)$으로 for문에 태워서 점화식을 계산하면 끝나는걸까? 당연히 아니다. $N$의 최댓값이 $10^{18}$라는 난관이 남아있다. 우리는 저 점화식을 $O(\log N)$으로 계산해내야 한다. 이를 위해 행렬의 제곱을 사용한다. 제곱 연산은 이전의 분할 정복을 활용해 $O(\log N)$으로 계산이 가능하다. 사실 비슷한 문제를 이미 분할 정복 단원에서 해결해봤다. 이번엔 식의 계수가 다르니 그 부분만 해결하면 된다.

점화식 $N_i=N_{i-1}\times 4-N_{i-2}$는 계수가 각각 $4$와 $-1$인 피보나치 수열이다. 따라서 피보나치 행렬을 수정할 필요가 있다. 피보나치 행렬을 구하는 과정은 다음과 같다.

$$\left(\begin{array}{c}{N}_i\\ N_{i-1}\end{array}\right)=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\left(\begin{array}{c}{N}_{i-1}\\ N_{i-2}\end{array}\right)=\left(\begin{array}{c}a\times N_{i-1}+b\times N_{i-2}\\ c\times N_{i-1}+d\times N_{i-2}\end{array}\right)$$ $$\begin{array}{r}{N}_i=a\times N_{i-1}+b\times N_{i-2}\\ N_{i-1}=c\times N_{i-1}+d\times N_{i-2}\end{array}$$

따라서 앞서 구한 점화식 $N_i=N_{i-1}\times 4-N_{i-2}$ 과 비교하면

$$a=4,b=-1,c=1,d=0$$

즉, $i$번째 답을 아래와 같이 표현할 수 있다.

$$\left(\begin{array}{c}{N}_i\\ N_{i-1}\end{array}\right)={\left(\begin{array}{cc}a=4& b=-1\\ c=1& d=0\end{array}\right)}^i\left(\begin{array}{c}{N}_1=3\\ N_0=1\end{array}\right)$$

여기서 피보나치 행렬을 $i$제곱하는 부분을 분할 정복을 활용해 $O(\log n)$에 계산하면 시간제한을 만족시킬 수 있다.

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
using ull = long long;
const ull mod = 1000000007;
 
vector<vector<ull>> mm(const vector<vector<ull>>& a, const vector<vector<ull>>& b) {
    vector<vector<ull>> ret(a.size(), vector<ull>(b[0].size(), 0));
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b[0].size(); j++) {            
            for (int k = 0; k < a.size(); k++) {
                ret[i][j] += (a[i][k] % mod * b[k][j] % mod) % mod;
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}
 
vector<vector<ull>> mpow(ull n, const vector<vector<ull>>& mat) {
    if (n == 0) return vector<vector<ull>>{ {1, 0}, {0, 1} }; 
    vector<vector<ull>> p1 = mpow(n / 2, mat);
    vector<vector<ull>> p2 = mm(p1, p1);
    if (n % 2 == 1) {
        return mm(p2, mat);
    }
    else {
        return p2;
    }
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        
    ull n; cin >> n;
    if (n % 2 == 1) {
        cout << 0;
        return 0;
    }
    n /= 2;    
    auto res = mm(mpow(n - 1, vector<vector<ull>>{ {4, -1}, { 1, 0 } }), vector<vector<ull>>{ {3}, { 1 } })[0][0];
    if (res < 0) res += mod;
    cout << res << "\n";    
    return 0;
}