키타마사법 (Kitamasa Method, きたまさ法)

점화식

\[ 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} \]

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

\[ 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) \tag 1 \]

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

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

다시 식 (1)에서 이번에는 $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) \]

두 번째에서 세 번째로 넘어가는 게 복잡한데, 열심히 계산 노가다 뛰면(?) 나옵니다. 그리고 또 다시(!) 식 (1)에서 $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} \]

이걸 식 (1)에 $p=2p$, $q=N$을 대입한 결과인

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

와 비교하면 아래 식이 나옵니다.

\[ 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} \tag 2 \]

여기서 $i=1$이면 우변의 앞쪽 합은 0인 걸로 합시다. (for (i = 1; i <= 0; i++)같은 느낌입니다.) 식 (2)에 의해 $A^{p-N}_{N,i}$를 구하면 $A^{2p-N}_{N,i}$를 구할 수 있다는 결론이 나옵니다. 즉,

  1. $v(p)$를 구하려면 $A^{p-N}_{N,i}$를 구해야 함.
  2. $A^{p/2-N}_{N,i}$를 구하면 $A^{p-N}_{N,i}$를 구할 수 있음.
  3. $A^{p/4-N}_{N,i}$를 구하면 $A^{p/2-N}_{N,i}$를 구할 수 있음.

결국 분할 정복으로 해결할 수 있다는 소리죠. 이때 기저 사례(base case)는 $A$의 지수가 0 이하가 될 때입니다. 즉, 식 (1)에서 $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}$로 나타내면 됩니다. 식 (1)에 $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} \]

따라서

\[ 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} \tag 3 \]

둘째, 식 (2)의 $A^j_{N,i}$를 구해야 합니다. 그냥 바로 위에 있는 식 (3)을 씁시다.

\[ \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}\]

따라서, 식 (2)와 식 (3)을 이용하면 이 문제를 분할 정복으로 풀 수 있습니다. 이를 키타마사법이라고 합니다.

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

응용

BOJ 15572:: 블럭 4

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

$v(p)$를 $N\times 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;
}