키타마사 법(kitamasa method, きたまさ法)에 대한 공부

1. 키타마사 법(kitamasa method)

 

수열 $a_{n}$의 점화식을 이전의 몇개 항으로 정의한다면, 귀납적 정의, 재귀적 수열 등으로 부른다.

 

$$a_{n} = \sum_{i = 1}^{k} w_{i}a_{n-i}$$

 

이런 형태로 정의되는 대표적인 수열은 피보나치 수열이다.

 

$$a_{n} = a_{n-1} + a_{n-2}, w_{1} = w_{2} = 1, k = 2$$

 

이 피보나치 수열의 가장 빠른? 해법중 하나는 행렬을 이용하는 방법이다.

 

https://deepdata.tistory.com/760

행렬을 이용한 피보나치 수열 문제의 해법

 

일반적으로 $a_{n} = \sum_{i = 1}^{k} a_{n-i}w_{i}$는 다음과 같은 행렬 표현으로 바꿀 수 있다.

 

 

이 방법의 시간복잡도는 $O(k^{3}logN)$으로 알려져있다.

 

이 방법도 나름 의미있지만, k = 1000정도 일때 세제곱이다보니 상당히 느려진다..

 

키타마사법의 목표는 $a_{n}$을 $O(k^{2}logN)$에 구하는 것이다.

 

 

2. 귀납적 수열의 n번항은 항상 1~k번 항의 선형결합으로 나타낼 수 있다

 

핵심 아이디어는 "이전의 k개의 항으로 결정되는" 수열의 점화식 $a_{n} = \sum_{i = 1}^{k} w_{i}a_{n-i}$에 대하여, 

 

$a_{n}$은 항상 "최초 k개의 항" $a_{1}, a_{2}, ... , a_{k}$의 선형 결합으로 나타낼 수 있다는 것이다.

 

$$a_{n} = \sum_{i = 1}^{k} a_{i}c_{i}$$

 

이 말이 무슨 말이냐면, 피보나치 수열 $a_{n} = a_{n-1} + a_{n-2}$에 대하여,

 

$$a_{3} = a_{1} + a_{2}, c_{1} = c_{2} = 1$$

 

$$a_{4} = a_{3} + a_{2} = a_{1} + 2a_{2}, c_{1} = 1, c_{2} = 2$$

 

$$a_{5} = a_{4} + a_{3} = a_{1} + 2a_{2} + a_{1} + a_{2} = 2a_{1} + 3a_{2}, c_{1} = 2, c_{2} = 3$$

 

...

 

이렇게 이전에 구한 항을 이용해서, n-1,n-2,... 항들을 소거하는 방식으로 항상 $c_{i}$를 찾을 수 있다.

 

만약에 수열 $c_{i}$를 빠르게 찾을 수 있다면, 원하는 $a_{n}$을 빠르게 구할 수 있을 것이다.

 

 

3. 다항식의 나눗셈으로의 접근

 

여러 블로그들을 찾아 읽어봤지만, 가장 쉬운 접근은 다항식의 나눗셈으로 접근하는 것 같다..

 

https://justicehui.github.io/hard-algorithm/2021/03/13/kitamasa/

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

 

https://milkclouds.work/linear-recurrence/

Linear Recurrence, 키타마사법

 

$a_{n}$의 점화식이 n이 k+1이상인 모든 자연수에 대해 다음과 같이 주어지면,

 

$$a_{n} = w_{1}a_{n-1} + w_{2}a_{n-2} + ... + w_{k}a_{n-k}$$

 

여기서 재귀적으로 $a_{n-1} = w_{1}a_{n-2} + w_{2}a_{n-3} + ... + w_{k}a_{n-1-k}$을 대입하면서 항을 소거하는 과정이

 

$a_{n} = x^{n}$으로 치환해서, 다항식처럼 생각한 다음

 

$$x^{n} = w_{1}x^{n-1} + w_{2}x^{n-2} + ... + w_{k}x^{n-k}$$

 

이것을 $x^{k} - w_{1}x^{k-1} - w_{2}x^{k-2} - ... - w_{k}x^{0}$으로 나눈 나머지를 구하는 과정과 동일하다는 것이다.

 

일반적인 식으로 해보면... 이게 되는건지 안되는건지 어려우니까 예를 들어 생각해보자.

 

가장 간단한 피보나치 수열 $a_{n} = a_{n-1} + a_{n-2}$의 n = 5에 대해 생각해보자.

 

$$a_{5} = a_{4} + a_{3} = (a_{3} + a_{2}) + a_{3} = 2a_{3} + a_{2}$$

 

$$a_{5} = 2a_{3} + a_{2} = 2(a_{2} + a_{1}) + a_{2} = 3a_{2} + 2a_{1}$$

 

$$a_{5} = 3a_{2} + 2a_{1} = 3(a_{1} + a_{0}) + 2a_{1} = 5a_{1} + 3a_{0}$$

 

만약 $a_{n} = x^{n}$라 하고, $a_{2} - a_{1} - 1 = x^{2} - x - 1$로 나눠보면...

 

$$x^{5} = (x^{3} + x^{2} + 2x + 3)(x^{2} - x - 1) + 5x + 3$$이다.

 

나머지 5x+3이 $a_{5} = 5a_{1} + 3a_{0}$와 동일하다.

 

그러므로, $a_{n}$을 구하는 문제는 $f(x) = x^{k} - w_{1}x^{k-1} - ... - w_{k}x^{0}$에 대하여, $x^{n} mod f(x)$를 구하는 문제가 된다. 

 

 

4. 구현 예시

 

곱셈과 나눗셈을 기본적인 구현 방법으로 구현하면, 항 수가 K개일때, $O(K^{2})$에 할 수 있다.

 

https://deepdata.tistory.com/981

다항식의 곱셈과 나눗셈 기본 컴퓨터 구현 방법 배우기

 

또한 N이 매우 크면 단순한 곱셈으로는 $x^{n}$을 구하는데 시간이 매우 오래걸린다.

 

하지만 분할 정복을 이용한 거듭제곱을 이용하면 $O(logN)$에 구할 수 있다.

 

이때, $x^{n} mod f(x)$를 구하는게 목표인데, 

 

$x^{n}$을 먼저 구할려고 배열로 [0,0,0,..........,1]로 만들면 공간 메모리 초과날것 같다

 

합동식의 성질 a*b mod p = (a mod p * b mod p) mod p로

 

거듭제곱 $x, x^{2}, x^{4}, ...$을 구하면서 나머지를 구하면 된다. 

 

또한 우리는 다항식의 나눗셈을 하면서 나머지만 필요로 한다. .. 몫은 return하지 않도록 한다.

 

전체 시간 복잡도가 $O(K^{2}logN)$에 해결할 수 있다.

 

#naive polynomial multiplication
def multiply(a,b,mod):

    result = [0]*(len(a)+len(b)-1)

    for i in range(len(a)):
        
        for j in range(len(b)):
            
            result[i+j] += (a[i]*b[j]) % mod
    
    return result

#negative mod

def negative_mod(x,mod):
    
    if x < 0:
        
        return (x+mod)%mod
    
    else:
        
        return x%mod
    
#naive polynomial division
#a/b
def divide(a,b,mod):
    
    q = [0]*(len(a)-len(b)+1) #몫

    #최고차항부터 순회해서..
    for i in range(len(q)-1,-1,-1):
        
        q[i] = a[i+len(b)-1]//b[-1]

        for j in range(len(b)-1,-1,-1):

            a[i+j] -= (q[i]*b[j])
            a[i+j] = negative_mod(a[i+j],mod)
    
    while a:
        
        x = a.pop()

        if x != 0:

            a.append(x)
            break

    return a

def kitamasa(w,a,n,mod):
    
    c = [1] #a_n = sum(w[i]a_n-i) = sum(c[i]a[i])
    x = [0,1] #x^1, x^2, x^4, ...
    
    #w를 이용해 f(x) = x^k - w1x^k-1 - w2x^k-2 - ...을 구한다.
    f = [negative_mod(-i,mod) for i in w]
    f.append(1)
    
    #분할정복을 이용한 거듭제곱으로 x^n mod f를 구한다.
    #합동식의 성질 a*b mod p = (a mod p * b mod p) mod p를 이용
    while n:
        
        if n & 1:
            
            c = divide(multiply(c,x,mod),f,mod)
            
        n >>= 1

        x = divide(multiply(x,x,mod),f,mod)
    
    #c배열을 찾았다면, an의 값을 구한다.
    #find a_n = sum(c[i]a[i])
    answer = 0

    for i in range(len(a)):

        answer += (a[i]*c[i])
        answer = negative_mod(answer,mod)

    return answer

 

 

5. 연습문제

 

11444번: 피보나치 수 6 (acmicpc.net)

11444번: 피보나치 수 6

 

w = [1,1]이고 a = [0,1]인 경우에 대한 키타마사법을 이용하면 해결할 수 있다.

 

FFT를 이용한 고속 곱셈을 하거나, 나눗셈도 빠른 나눗셈을 사용하지 않는 이상... 당장 실전성은 없는듯하다...

 

혹은 최신 알고리즘으로 보스턴 모리 알고리즘을 쓰지 않는 이상은... 필요가 없는것 같다