프로그래밍 연습장

키타마사 법 본문

알고리즘

키타마사 법

김준원 2018. 3. 25. 10:09

재귀적 수열은 어떤 $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$의 값을 알 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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+10); 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+10);
        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+10);
            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);
}
 
cs


참조: #


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

'알고리즘' 카테고리의 다른 글

Ray Casting Algorithm  (5) 2019.07.21
Skip List  (2) 2018.03.31
Manacher의 알고리즘과 Z 알고리즘  (0) 2018.02.27
그래프의 간선 리스트 표현  (2) 2017.12.06
Heavy Light Decomposition의 구현  (0) 2017.12.03
Comments