서론
키타마사법(Kitamasa Method, きたまさ法)은 AN=c1AN−1+c2AN−2+⋯+cKAN−K=∑Ki=1ciAN−i와 같은 선형 점화식의 N번째 항을 O(K2logN), 더 나아가 O(KlogKlogN)에 계산하는 알고리즘입니다.
이 글에서는 키타마사법을 최대한 쉽게 설명하는 것에 초점을 두기 때문에 엄밀한 증명이 생략될 수 있습니다. 양해 부탁드립니다.
식의 변형
키타마사법의 목표는 이전 K개의 항으로 결정되는 AN=∑Ki=1ciAN−i 꼴의 점화식을 최초 K개의 항으로 결정되도록 하는 AN=∑K−1i=0diAi 꼴의 식을 찾는 것입니다. 이 식을 만족시키는 수열 di를 T(N,K) 시간에 찾을 수 있다면, 단순히 ∑K−1i=0diAi를 계산하면 되므로 점화식의 N번째 항을 O(T(N,K)+K) 시간에 계산할 수 있습니다.
이러한 수열 di는 항상 존재하며, 적절한 식을 대입해 AN−1,AN−2,⋯를 소거하는 방식으로 직접 찾을 수 있습니다. 그 예시로, BOJ 1003번 피보나치 수열 문제는 c1=c2=1일 때(피보나치 수열) di를 찾는 문제입니다.
c1=2,c2=1이고 N=5일 때의 di를 직접 구해보며 어떻게 하면 효율적으로 계산할 수 있을지 고민해봅시다.
- A5=2A4+A3
- A5=2(2A3+A2)+A3=5A3+2A2
- A5=5(2A2+A1)+2A2=12A2+5A1
- A5=12(2A1+A0)+5A1=29A1+12A0
- d0=12,d1=29가 됩니다.
사실 이 과정은 양변에 Ax−c1Ax−1−c2Ax−2−⋯=0의 상수배를 빼는 과정이라고 생각해볼 수 있습니다. 위 예시에서는 Ax−2Ax−1−Ax−2=0의 상수배를 빼게 되겠지요.
- A5=2A4+A3, 양변에서 2(A4−2A3−A2)=0을 빼면
- A5=5A3+2A2, 양변에서 5(A3−2A2−A1)=0을 빼면
- A5=12A2+5A1, 양변에서 12(A2−2A1−A0)=0을 빼면
- A5=29A1+12A0
이 과정은 xN을 f(x)=xK−c1xK−1−c2xK−2−⋯−cKx0=xK−∑Ki=1cixK−i로 나눈 나머지를 구하는 과정과 완벽하게 동일합니다. 위 예시는 사실 x5를 x2−2x−1로 나눈 나머지를 구하는 과정이었고, 실제로 x5=(x3+2x2+5x+12)(x2−2x−1)+29x+12입니다.
우리는 이제 x^N \mod f(x)를 빠르게 계산하는 방법을 알면 됩니다.
분할 정복을 이용한 거듭 제곱
키타마사법을 사용해야하는 문제는 대부분 N이 매우 크기 때문에 x^N을 그대로 다룰 수 없습니다. 우리는 어떤 수의 거듭 제곱은 O(\log N)에 구할 수 있으니, 이 방법을 응용해봅시다.
x^N은 x^1, x^2, x^4, x^8, \cdots들의 곱으로 표현할 수 있고, 총 O(\log N)번의 다항식 곱셈을 요구하게 됩니다. x^N \mod f(x)를 구하는 것이 목표이기 때문에, (x^1 \mod f(x)), (x^2 \mod f(x)), (x^4 \mod f(x)) 들의 곱을 f(x)로 나눈 나머지를 구하면 됩니다. mod\ f(x)를 취하면 차수가 K 미만이기 때문에, 차수가 K 미만인 두 다항식끼리의 곱셈과 나눗셈을 각각 O(\log N)번 수행하게 됩니다.
아래와 같이 구현하면, 키타마사법의 시간 복잡도는 Mul함수와 Div함수의 시간 복잡도에 따라 결정됩니다. 구체적으로, Mul함수와 Div함수의 시간 복잡도가 P(K)일 때 키타마사법의 시간 복잡도는 O(P(K) \log N)이 됩니다.
1 |
|
O(K^2 \log N) 키타마사법
다항식의 곱셈과 나눗셈을 Naive하게 구현하면 O(K^2) 시간이 걸리므로 이때 키타마사법의 시간 복잡도는 O(K^2 \log N)이 됩니다. 아래 코드는 BOJ 11444번 피보나치 수 6 문제의 정답 코드입니다.
1 |
|
O(K \log K \log N) 키타마사법
O(K^2 \log N)을 O(K \log K \log N)로 최적화시키는 방법은 당연히 다항식의 곱셈과 나눗셈을 O(K \log K)에 수행하는 것입니다.
FFT를 이용해 다항식의 곱셈을 O(K \log K)에 수행하는 방법은 제 블로그에 올라와있고, 비슷하게 FFT를 이용해 다항식의 나눗셈을 O(K \log K)에 수행하는 방법은 삼성 소프트웨어 멤버십 블로그에 잘 설명되어 있습니다.
NTT를 이용해 키타마사법을 O(K \log K \log N)에 수행하는 코드를 첨부하고 글을 마무리하겠습니다.
1 |
|
참고 자료
- algoshitpo(by ahgus89) - Linear Recurrence (https://algoshitpo.github.io/2020/05/20/linear-recurrence/)
- junis3 - 키타마사 법 (https://blog.junie.land/27)
- 삼성소프트웨어멤버십(by cubelover) - 빠른 다항식 나눗셈 (http://www.secmem.org/blog/2019/04/10/polynomial-division/)
- koosaga github - algebra.cpp (https://github.com/koosaga/olympiad/blob/master/Library/codes/math/algebra.cpp)