서론
키타마사법(Kitamasa Method, きたまさ法)은 $A_N = c_1A_{N-1} + c_2A_{N-2} + \cdots + c_KA_{N-K} = \sum_{i=1}^{K} c_iA_{N-i}$와 같은 선형 점화식의 $N$번째 항을 $O(K^2 \log N)$, 더 나아가 $O(K \log K \log N)$에 계산하는 알고리즘입니다.
이 글에서는 키타마사법을 최대한 쉽게 설명하는 것에 초점을 두기 때문에 엄밀한 증명이 생략될 수 있습니다. 양해 부탁드립니다.