키타마사법 (Kitamasa method)

참고 : http://cubelover.tistory.com/21

Kitamasa법은 다음과 같이 계수가 결정된 선형 점화식을 갖는 수열의 \(n\)번째 항을 빠르게 결정할 수 있는 방법이다.

$$ a_n = c_1 \cdot a_{n-1} + c_2 \cdot a_{n-2} + \cdots c_m \cdot a_{n-m} = \sum_{i=1}^{m}c_{i}a_{n-i} $$

Naive로 풀면 \(O(nm)\) 정도의 시간이 걸리고, 

$$ \color{red}{\begin{pmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{n-m+1}  \end{pmatrix}} = \color{blue}{\begin{pmatrix} c_1 & c_2 & \cdots & c_{m} \\  &  &  & 0 \\  & I &  & \vdots \\  &  &  & 0 \end{pmatrix}} \cdot \color{green}{\begin{pmatrix} a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{n-m}  \end{pmatrix}} $$

$$ = \color{red}{v_n} = \color{blue}{M} \cdot \color{green}{v_{n-1}} $$

이와 같이 점화식을 행렬곱으로 나타낼 수 있음을 이용하여 \(M, M^2, M^4, \cdots\) 들을 미리 구해 두고 이진법으로 \(n\)번째 항을 구하면

시간 : \(O(m^3 \lg n) \) \((\text{Optimized} : O(m^\omega \lg n))\)

메모리 : \(O(m^2 \lg n)\)

정도로, 대부분의 DP 문제에서 이 이상을 요구하진 않는다.

하지만 키타마사법을 이용하면 \(O(m^2\lg n)\), 심지어는 \(O(m\lg m \lg n)\)이라는 괴악한 시간복잡도를 만들어 낼 수 있다.

핵심 아이디어는 다음과 같다 : 

모든 \(n\) 에 대해서, \(a_n\)은 초기항 \(a_1 , \cdots a_m\)의 선형결합으로 나타낼 수 있다. 즉, \(a_n = \sum_{i=1}^{m} a_i d_i\)이다.

그런데 어차피 \(v_n = M^{n-m}v_m\)이고, 수열 \(d\)는 행렬 \(M^{n-m}\)의 제 1행일 뿐이다. 

따라서 임의의 자연수 \(h\)에 대해서 \(v_{n+h} = M^{n-m} v_{m+h}\)가 성립하고,

이는 \(a_{n+h} = \sum_{i=1}^{m} a_{i+h} d_i\)가 성립함을 의미한다.

따라서 \(a_{2n} = a_{n+n} = \sum_{i=1}^{m} a_{i+n}d_i = \sum_{i=1}^{m}\sum_{j=1}^{m} a_{i+j}d_i d_j\)가 되고, 따라서 \(a_{2n}\)을 \(a_1 \cdot a_{2m} \)의 식으로 나타내는 데에 성공했다.

계수인 \(\sum d_i d_j \)를 단순하게 구하면 \(O(m^2)\), FFT를 사용하면 \(O(m \lg m)\)만에 구할 수 있다.

마찬가지로 \(a_{m+1} \cdots a_{2m}\)의 계수를 \(a_1 \cdots a_m\)의 계수로 \(O(m\lg m)\)보내줄 수가 있는데, 얘는 documentation이 죄다 일본어라서(...) 나중에 업데이트하기로 한다. naive로는 \(O(m^2)\)에 할 수 있다.

결국 최종적으로 \(a_n\)의 정보를 \(a_{2n}\)으로 바꾸는 데에 \(O(m \lg m)\)의 시간이 걸리므로 시간복잡도는 \(O(m \lg m \lg n)\)이다.