https://www.acmicpc.net/problem/15572

설명

일정한 구간을 타일로 채우는 문제. 어디선가 매우 많이 본 것 같은 문제이다. 차근차근 처음부터 살펴보자.

우리는 현재 `N×(1~N)`의 블록을 가지고 있다. 그리고 `N×M`형태의 모양을 만들어야 한다. 블록은 어떻게든 놓을 수 있지만, 일단 `N>M`인 형태부터 먼저 살펴보겠다.

`M`이 `N`보다 작고 `N`이 세로라고 가정한다면, 우리는 블록을 세로로 밖에 놓을 수 없다. 그렇다면 이때의 경우의 수는 `M`이라는 수를 여러 수로 쪼개는 경우의 수라고 생각할 수 있다. 조금 더 비유를 하자면, 1이 `M`개 있을 때, 그 사이에 칸막이를 넣는지 안 넣는지에 대한 경우의 수로 나타낼 수 있으며, `N`보다 작은 `M`에 대하여 그 개수는 \(2^{M-1} (M<N)\) 라고 표현할 수 있다. 만약 `N`이랑 `M`이 같을 경우는 이제 블록을 90도 회전해서 넣어도 되므로, 경우의 수가 2배로 늘고, `N×N` 블록의 수만 제외해 주면 되므로 \(2^N-1 (M = N)\) 가 된다.

이제 이 사실을 바탕으로 다음으로 넘어가 보자. 이제 앞으로 `N×k`개의 블록을 채우는 경우의 수를 `A_k`라고 칭하겠다. 그렇다면 이제 `N`보다 큰 `M`에 대해서 다음과 같이 생각해 볼 수 있겠다.

\[A_M = \sum\limits_{i=1}^N A_{i}A_{M-i}\]

즉, 전체의 구간을 나눠서 생각을 하겠다는 것이다. `N`이하의 `M`에 대해서는 명확히 우리가 구할 수 있고, 아닌 수에 대해서는 N이하 경우의 수의 곱으로 나타낼 수 있기에 다음과 같은 식을 도출할 수 있다. 하지만 과연 이 식이 맞을까?

아쉽게도 이 식은 중복된 경우의 수를 카운트한다. `N×1`과 `N×2`의 케이스를 한번 살펴보자. `N×1`를 만드는 경우는 딱 하나다. `N×1`하나만 틱 놓는 것. `N × 2`는 `N × 1` 2개를 놓는 것과 `N × 2` 하나를 놓는 것 총 2가지의 경우가 있다. 이때 `N×2`에서 `N×1` 2개를 놓은 경우의 수는 `N×1`의 경우의 수와 겹치게 된다.

따라서 이런 식으로 접근하려면, `N×k(1<=k<=N)`를 앞선 경우의 수와 차별되게 놓아야 한다. 이제 `C_k`를 다음과 같이 정의하자.

`C_k =` `k`보다 작은 `j`에 대하여, `N×j`를 만들 때 사용한 경우의 수를 포함하지 않는 `N×k`를 만드는 경우의 수.

그렇다면 우리가 새로한 `C_k`를 가지고 다시 식을 고쳐 쓸 수 있다. 전체 경우의 수는

\[A_M = \sum\limits_{i=1}^N C_{i}A_{M-i}\]

가 된다. 이제 `C_k`를 다시 살펴보자. 말은 저렇게 복잡하게 했지만, 실제로 유일하게 만들 수 있는 경우의 수는 `N×k`만 놓는 경우의 수 딱 하나밖에 없다. 예외로 `N×N`의 크기는 가로로 뒤집을 수도 있으니 따로 처리해주고, 전체 `C_K`는 다음과 같다.

\[C_K = \begin{cases} 1 & (K < N) \\ 2^{N-1} & (K = N) \end{cases}\]

그리고 `A_K`는

\[A_K = \begin{cases} 2^{K-1} & (K < N) \\ 2^{N} - 1 & (K = N) \end{cases}\]

로 나타낼 수 있다.

이제 저런 형식의 점화식은 수가 적당히 작다면 분할정복을 이용한 거듭제곱을 통해 행렬을 곱해서 구할 수 있지만, 현재 이 문제의 수 제한은 큰 편이므로 이 점화식을 이용해 빠르게 특정 항을 구할 수 있는 키타마사법을 사용하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr ll DIV = 1999;
constexpr int LEN = 100001;
ll A[LEN],C[LEN],D[LEN],T[LEN<<1];

void Kitamasa(ll N,int M) {
    if(N == 1) {
        D[1] = 1;
        for(int i=2; i<=M; i++) D[i] = 0;
        return;
    }
    if(N&1) {
        Kitamasa(N^1,M);
        int j = D[M];
        for(int i=M; i>=1; i--) D[i] = (D[i-1] + C[M-i+1]*j)%DIV;
    } else {
        Kitamasa(N>>1,M);
        for(int i=1; i<=M+M; i++) T[i] = 0;
        for(int i=1; i<=M; i++) for(int j=1; j<=M; j++) T[i+j] = (T[i+j] + D[i]*D[j])%DIV;
        for(int i=M+M; i>M; i--) for(int j=1; j<=M; j++) T[i-j] = (T[i-j] + C[j]*T[i])%DIV;
        for(int i=1; i<=M; i++) D[i] = T[i];
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    ll N,M;
    cin >> N >> M;
    if(N == 1) cout << 1,exit(0);

    A[1] = 1;
    C[1] = 1;
    for(int i=2; i<N; i++) {
        A[i] = (A[i-1]*2)%DIV;
        C[i] = 1;
    }
    A[N] = ((A[N-1]*4)%DIV-1)%DIV;
    C[N] = (A[N-1]*2)%DIV;


    Kitamasa(M,N);
    ll ans = 0;
    for(int i=1; i<=N; i++) ans = (ans + A[i]*D[i])%DIV;
    cout << ans;
}

여담

키타마사법에 대한 설명은 다른 곳에 해두겠다…. 그리고 이 문제의 하위 문제인 블록 1~3까지도 풀 수 있으니 참고바란다.