키타마사법

점화식

\[ v(p) = c(1)v(p-N) + c(2)v(p-N+1) + \cdots + c(N)v(p-1) \]

을 갖는 수열 ${v(p)}$를 생각해봅시다. 초기값이 주어진다면 동적계획법으로 $M$번째 항을 $O(M)$안에 구할 수 있지만 익히 알려져있다시피

\[ \underbrace{ \begin{bmatrix} 0 & 1 & \cdots & 0 \\ \vdots && \ddots & \\ 0 & 0 & \cdots & 1 \\ c(1) & c(2) & \cdots & c(N) \end{bmatrix} }_A \begin{bmatrix} v(p-N) \\ \vdots \\ v(p-2) \\ v(p-1) \end{bmatrix} = \begin{bmatrix} v(p-N+1) \\ \vdots \\ v(p-1) \\ v(p) \end{bmatrix} \]

처럼 행렬 형태로 쓰면 빠른 거듭제곱 알고리즘으로 $O(N^3\log M)$ 안에 풀 수 있게 됩니다. 하지만 이건 $N$이 작을 때나 더 빠른 방법이고, $N$이 1000 정도만 되어도 $N^3$이라 계산 시간이 너무 늘어납니다.

위 식을 살짝 바꿔서 정수 $p$, $q$에 대해($p>q$)

\[ A^{p-q} \begin{bmatrix} v(q-N+1) \\ \vdots \\ v(q) \end{bmatrix} = \begin{bmatrix} v(p-N+1) \\ \vdots \\ v(p) \end{bmatrix} \]

양변의 마지막 행만 비교하면

\begin{equation} v(p) = A^{p-q}_{N,1} v(q-N+1) + \cdots + A^{p-q}_{N,N} v(q) = \sum_{i=1}^N A^{p-q}_{N,i} v(q-N+i) \label{eq:eq1} \end{equation}

여기서 $A^n_{i,j}$는 $A^n$의 $i$행 $j$열 성분을 말합니다. 식 \eqref{eq:eq1}은 임의의 $p$, $q$에 대해 성립하므로 $p$에는 $2p$, $q$에는 $p+q$를 대입해봅시다.

\[ v(2p) = \sum_{i=1}^N A^{p-q}_{N,i} v(p+q-N+i) \]

다시 식 \eqref{eq:eq1}에서 이번에는 $p$에 $p+q−N+i$, $q$에 $2q−N+i$를 대입해봅시다.

\[ v(p+q-N+i) = \sum_{j=1}^N A^{p-q}_{N,j} v(2q-2N+i+j) \]

두 식을 조합하면

\[ v(2p) = \sum_{i=1}^N \sum_{j=1}^N A^{p-q}_{N,i} A^{p-q}_{N,j} v(2q-2N+i+j) \]

여기에 $q=N$을 대입하면

\[ v(2p) = \sum_{i=1}^N \sum_{j=1}^N A^{p-N}_{N,i} A^{p-N}_{N,j} v(i+j) = \sum_{i=2}^N \sum_{j=1}^{i-1} A^{p-N}_{N,j} A^{p-N}_{N,i-j} v(i) + \sum_{i=1}^N \sum_{j=i}^N A^{p-N}_{N,j} A^{p-N}_{N,i-j+N} v(i+N) \]

두 번째에서 세 번째로 넘어가는 게 복잡한데, 열심히 계산하면 유도 가능합니다. 그리고 또 다시 식 \eqref{eq:eq1}에서 $p=i+N$, $q=N$을 대입합시다.

\[ v(i+N) = \sum_{k=1}^N A^i_{N,k} v(k) \]

이걸 위 식에 대입하면

\begin{align*} v(2p) &= \sum_{i=2}^N \sum_{j=1}^{i-1} A^{p-N}_{N,j} A^{p-N}_{N,i-j} v(i) + \sum_{i=1}^N \sum_{j=i}^N \sum_{k=1}^N A^{p-N}_{N,j} A^{p-N}_{N,i-j+N} A^i_{N,k} v(k) \\ &= \sum_{i=2}^N \sum_{j=1}^{i-1} A^{p-N}_{N,j} A^{p-N}_{N,i-j} v(i) + \sum_{i=1}^N \sum_{j=1}^N \underbrace {\left[ \sum_{k=j}^N A^{p-N}_{N,k} A^{p-N}_{j-k+N} \right]}_{b(j)} A^j_{N,i} v(i) \end{align*}

이걸 식 \eqref{eq:eq1}에 $p=2p$, $q=N$을 대입한 결과인

\[ v(2p) = \sum_{i=1}^N A^{2p-N}_{N,i} v(i) \]

와 비교하면 다음 식을 얻습니다.

\begin{equation} A^{2p-N}_{N,i} = \sum_{j=1}^{i-1} A^{p-N}_{N,j} A^{p-N}_{N,i-j} + \sum_{j=1}^N b(j) A^j_{N,i} \label{eq:eq2} \end{equation}

여기서 $i=1$이면 우변의 앞쪽 합은 0인 걸로 합시다. 식 \eqref{eq:eq2}에 의해 $A^{p−N}{N,i}$를 구하면 $A^{2p−N}{N,i}$를 구할 수 있다는 결론이 나옵니다. 즉,

$A_{N,i}^{p-N}$를 구하면 $v(p)$를 구할 수 있습니다.
$A_{N,i}^{p/2-N}$를 구하면 $A_{N,i}^{p-N}$를 구할 수 있습니다.
$A_{N,i}^{p/4-N}$를 구하면 $A_{N,i}^{p/2-N}$를 구할 수 있습니다.
…

결국 분할 정복으로 구할 수 있다는 소리죠. 이때 기저 사례(base case)는 $A$의 지수가 0 이하가 될 때입니다. 이는 식 \eqref{eq:eq1}에서 $p\le N$, $q=N$인 경우로, 양변을 비교하면

\[ A^{p-N}_{N,i} = \begin{cases} 0 & p \neq i \\ 1 & p = i \end{cases} \]

이제 생각할 건 두 가지입니다.

첫째, $p$가 홀수인 경우입니다. $p−1$은 짝수이므로 $A^{p−N}{N,i}$를 $A^{p−N−1}{N,i}$로 나타내면 됩니다. 식 \eqref{eq:eq1}에 $q=N+1$을 대입해 봅시다.

\[ v(p) = \sum_{i=1}^{N-1} A^{p-N-1}_{N,i} v(i+1) + A^{p-N-1}_{N,N} v(N+1) \]

$v(N+1)$에 점화식을 대입하면

\begin{align*} v(p) &= \sum_{i=1}^{N-1} A^{p-N-1}_{N,i} v(i+1) + A^{p-N-1}_{N,N} \sum_{i=1}^N c(i) v(i) \\ &= c(1) A^{p-N-1}_{N,N} v(1) + \sum_{i=2}^N \left [ A^{p-N-1}_{N,i-1} + c(i) A^{p-N-1}_{N,N} \right ] v(i) \end{align*}

따라서

\begin{equation} A^{p-N}_{N,i} = \begin{cases} c(1) A^{p-N-1}_{N,N} & i=1 \\ A^{p-N-1}_{N,i-1} + c(i) A^{p-N-1}_{N,N} & i \ge 2 \end{cases} \label{eq:eq3} \end{equation}

둘째, 식 \eqref{eq:eq2}의 $A^j_{N,i}$를 구해야 합니다. 그냥 바로 위에 있는 식 \eqref{eq:eq3}을 씁시다.

\begin{align*} \text{for } j = 1, \qquad A_{N,i} &= c(i) \\ \text{for } j \ge 2, \qquad A^j_{N,i} &= \begin{cases} c(1) A^{j-1}_{N,N} & i=1 \\ A^{j-1}_{N,i-1} + c(i) A^{j-1}_{N,N} & i \ge 2 \end{cases} \end{align*}

따라서, 식 \eqref{eq:eq2}와 식 \eqref{eq:eq3}을 이용하면 이 문제를 분할 정복으로 풀 수 있습니다. 이를 키타마사법(Kitamasa method)이라고 합니다.

시간 복잡도를 계산해보면 식 \eqref{eq:eq2}를 써서 $v(p)$에서 $v(2p)$를 구하는 데 $O(N^2)$이 걸립니다. 이때 각 j에 대해 $b(j)$를 미리 계산해둡니다. 또 식 \eqref{eq:eq3}을 써서 $v(p−1)$에서 $v(p)$를 구하는 데 $O(N)$이 걸리고, $A^j_{N,i}$는 $O(N^2)$의 전처리로 역시 미리 구해둡니다. 따라서 키타마사법의 시간복잡도는 $O(N^2\log M)$입니다.

응용

BOJ 15572:: 블럭 4

$v(p)$를 $N×p$ 모양을 만드는 가짓수라고 하면 다음 점화식이 성립합니다.

\[ v(p)=\begin{cases} 2^{p-1}, & p < N \\ 2^N-1, & p = N \\ 2^{N-1} v(p-N) + v(p-N+1) + v(p-N+2) + \cdots + v(p-1), & p > N \end{cases} \]

키타마사법을 그대로 적용해주면 됩니다.


#include<bits/stdc++.h>

using namespace std;

int n;
long long m;
int v[1001] = {0, 1}, c[1001], an[1001][1001];
int a[1001], t[1001], b[1001];

void kitamasa(long long p) {
    if (p <= n) {
        fill(a+1, a+n+1, 0);
        a[p] = 1;
        return;
    }
    if (p % 2 == 1) {
        kitamasa(p-1);
        int last = a[n];
        for (int i = n; i >= 1; i--)
            a[i] = (a[i-1] + c[i] * last) % 1999;
        return;
    }
    kitamasa(p/2);
    fill(t+1, t+n+1, 0);
    fill(b+1, b+n+1, 0);
    for (int j = 1; j <= n; j++)
        for (int k = j; k <= n; k++)
            b[j] = (b[j] + a[k] * a[j-k+n]) % 1999;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i-1; j++)
            t[i] = (t[i] + a[j] * a[i-j]) % 1999;
        for (int j = 1; j <= n; j++)
            t[i] = (t[i] + b[j] * an[j][i]) % 1999;
    }
    copy(t+1, t+n+1, a+1);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;

    for (int i = 2; i <= n; i++)
        v[i] = (2 * v[i-1]) % 1999;
    v[n] = (2 * v[n] - 1) % 1999;

    fill(c+1, c+n+1, 1);
    for (int i = 1; i < n; i++)
        c[1] = (2 * c[1]) % 1999;

    copy(c+1, c+n+1, an[1]+1);
    for (int j = 2; j <= n; j++)
        for (int i = 1; i <= n; i++)
            an[j][i] = (an[j][i] + an[j-1][i-1] + c[i] * an[j-1][n]) % 1999;

    kitamasa(m);

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + a[i] * v[i]) % 1999;

    cout << res;

    return 0;
}

Algorithm