키타마사 법

재귀적 수열은 어떤 $k$에 대해 $n>k$라면 $a_n = \sum _{i=1}^k w_i a_{n-i}$가 성립하는 수열을 뜻한다. 가장 간단한 재귀적 수열은 피보나치 수열로, $k=2$, $w = [1, 1]$인 수열이다.

행렬의 제곱을 이용해 재귀적 수열의 $n$번째 항을 빠르게 구할 수 있다. $a_n$을 그 전 $k$개 항의 선형 결합으로 나타내어 보면, 매 항에 대해서 선형 결합의 형태가 같음을 확인할 수 있다. 따라서 같은 행렬을 $n$여 번 곱하는 형태로 $a_n$에 대한 식을 구할 수 있으며, 이는 단순한 알고리즘으로 $O(k^3 \log n)$의 시간 복잡도로 문제를 해결할 수 있게 한다.

더 빠른 방법이 있다: 키타마사 법(Kitamasa method, きたまさ法)로 불리는 방법으로 시간 복잡도인 $O(k^2 \log n)$에 임의의 항을 구할 수 있다. 피보나치 같이 $k=2$ 정도로 작으면 무관하지만, 거대한 귀납적 수열에서는 성능을 크게 향상시킬 수 있다.

키타마사 법의 핵심 아이디어는, 수열의 원소 $a_n$은 항상 어떠한 형태로 $a_{1..k}$의 정수 배의 합으로 나타내어진다는 것이다:

$c_{1..k}$가 존재해, $a_n = \sum_{i=1}^k a_i c_i$

따라서, 다음이 성립한다.

$$a_{2n} = \sum_{i=1}^k a_{n+i} c_i = \sum_{i=1}^k \sum_{j=1}^k a_{i+j} c_i c_j$$

그리고, 

$$a_{n+1} = \sum_{i=1}^k a_{i+1} c_i = w_k c_k a_1 + \sum_{i=2}^k (c_{i-1} + w_{k+1-i} c_k ) a_i $$

또한 성립한다. 따라서, $a_n$의 $c_{1..k}$ 표현을 알고 있으면 $O(k^2)$에 $a_{2n}$의 $c_{1..k}$ 표현을, $O(k)$에 $a_{n+1}$의 $c_{1..k}$ 표현을 얻을 수 있다. $a_1$은 $c_{1..k} = [1, 0, \cdots , 0]$을 가지므로, 총 $O(k^2 \log n)$에 $a_n$의 $c_{1..k}$ 표현을 구할 수 있고, 이로부터 빠르게 $a_n$의 값을 알 수 있다.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lint;
const int mod = 1000000007;
int k, a[1004], w[1004];
 
int add(int x, int y) { return (x+y) % mod; }
int mul(int x, int y) { return (x*(lint)y) % mod; }
 
int kitamasa(lint n) {
    vector<int> c(k+1, 0); c[1] = 1;
 
    // n = 1 만들기
    int b = 62;
    while ((n>>b)%2==0) b--;
 
    for (b--; ~b; b--) {
        // c(n) -> c(2n)
        vector<int> d(2*k+1, 0);
        for (int i=1; i<=k; i++) for (int j=1; j<=k; j++) d[i+j] = add(d[i+j], mul(c[i], c[j]));
        for (int i=2*k; i>k; i--) for (int j=1; j<=k; j++) d[i-j] = add(d[i-j], mul(d[i], w[j]));
        d.resize(k+1);
        c = d;
        // c(n) -> c(n+1)
        if ((n>>b)&1) {
            vector<int> d(k+1, 0);
            d[1] = mul(c[k], w[k]);
            for (int i=2; i<=k; i++) d[i] = c[i-1] + mul(c[k], w[k+1-i]);
            c = d;
        }
    }
 
    int ans = 0;
    for (int i=1; i<=k; i++) ans = add(ans, mul(a[i], c[i]));
    return ans;
}
 
int main()
{
    lint n;
    cin >> n >> k;
    for (int i=1; i<=k; i++) cin >> a[i]; // 첫 k개의 항
    for (int i=1; i<=k; i++) cin >> w[i]; // 점화식의 계수
 
    cout << kitamasa(n);
}
 

참조: #

고속 푸리에 변환을 응용한 방법으로 전이 과정을 $O(k \log k)$에 수행할 수도 있다. 이를 고속 키타마사법이라고 따로 이름 붙이기도 하나 보다. 이로서 같은 문제를 $O(k \log k \log n)$의 시간에 해결할 수도 있다. #