Linear Recurrence, 키타마사법
다음과 같이 정의되는 무한수열 $a_n$이 있다고 하자.
\[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}\]
$c$와 $a$의 $k$개의 초항이 주어졌을 때 $a_n$을 빠르게 구하는 게 하고 싶은 일이다.
1. 행렬곱
행렬곱을 통해 $O(k^3\log{n})$만에 계산이 가능하다.
2. kitamasa
2.1 키타마사법의 고교수준 유도
\[a_n=d_1 a_1 + d_2 a_2 + \ldots+ d_k a_k\]
$a_n$을 $a_1, a_2, \ldots, a_k$로 나타내면 위와 같다. (점화식이 선형이므로 이와 같은 꼴로 나타낼 수 있다.) $d_i$를 빨리 구할 수 있다면 $a_n$ 역시도 빠르게 구할 수 있을 것이다.
점화식에 의해 $a_{n} - c_1 a_{n-1} - c_2 a_{n-2} - \ldots - c_k a_{n-k}=0$이다. $a_{n} - c_1 a_{n-1} - c_2 a_{n-2} - \ldots - c_k a_{n-k}$를 $P_n$으로 두면
\[\forall n\ge k+1, P_n=0\]
\[a_n=(1 \cdot P_n + b_2 P_{n-1}+ \ldots + b_{n-k} P_{k+1}) + (d_1 a_1 + d_2 a_2 + \ldots+ d_k a_k)\\ \because (1 \cdot P_n + b_2 P_{n-1}+ \ldots + b_{n-k} P_{k+1})=0\]
이를 다르게 나타내면 아래와 같다. $a_n$을 $x^{n-1}$에 대응시켰다.
\[x^{n-1}= (b_1 x^{n-k-1} + b_2 x^{n-k-2}+ \ldots)(x^k - c_1 x^{k-1} - c_2 x^{k-2} - \ldots - c_k x^{0}) + (d_1 x^0+d_2 x^1+\ldots+d_k x^{k-1})\]
$x^{n-1}$을 $P(x)=x^k - c_1 x^{k-1} - c_2 x^{k-2} - \ldots - c_k x^{0}$로 나누면
\[x^{n-1}=P(x)Q(x)+R^\prime(x)\]
나눗셈 정리에 의해 나눈 몫 $Q(x)$과 나머지 $R^\prime(x)$는 유일하다. 따라서 $R^\prime(x)=R(x)$이고, $d_i$를 구하기 위해선 $x^{n-1}$을 $P(x)=x^k - c_1 x^{k-1} - c_2 x^{k-2} - \ldots - c_k x^{0}$로 나눈 나머지만 구해도 된다는 사실을 알 수 있다.
2.2 키타마사법 유도(대학교 수준)
\[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}\]
위 점화식을 따르는 $a_n$의 특성방정식이 $x^{k+1}-c_1 x^{k}-c_2 x^{k-2}-\ldots-c_k x^0=0$이며, 특성방정식의 근이 $r_1, r_2, \ldots, r_k$일 때 $a_n$은 $r_{1}^{n}, r_{2}^{n}, \ldots, r_{k}^{n}$들의 선형결합으로 나타남이 잘 알려져 있다. (내용이 부실해도 간단하게 설명하면, 각 해가 점화식을 만족하고, 선형독립이므로 이들의 선형결합으로 해공간이 구성되며, $a_1, a_2, \ldots a_k$의 변화에 따라 $a_n$이 변하므로 $k$차원이기에 $k$개 기저를 찾으면 그게 기저가 된다.)
\[a_n=b_1 r_{1}^{n} + b_2 r_{2}^{n} + \ldots +b_k r_{k}^{n}=\sum _{i} b_{i} r_{i}^{n}\]
우리는 $a_n=d_1 a_1 + d_2 a_2 + \ldots+ d_k a_k$일 때, $d_i$를 구하길 원하므로
\[\begin{align}a_n&=\sum_{i} b_{i} r_{i}^n\\ &= \sum_{i} d_{i} a_{i}\\&= \sum_{i} d_{i} \sum_{j} b_{j} r_{j}^{i} \\ &= \sum_{j} b_{j} \sum_{i} r_{j}^{i} d_{i} \end{align}\]
따라서 $r_{i}^{n}=\sum_{j} r_{i}^{j} d_{j}$
이러한 조건을 만족하는 $r_1, r_2, \ldots r_k$는 $x^{n-1}=\prod_i (x-r_i) Q(x)+\sum_{j} d_j x^{j-1}$를 만족한다.
$\prod_i (x-r_i)$는 $k$차 다항식, $\sum_{j} d_j x^{j-1}$는 $k-1$차 다항식이므로 $x^{n-1}$를 $P(x)=\prod_i (x-r_i)$로 나눈 나머지가 $R(x)=\sum_{j} d_j x^{j-1}$이다.
근데 중근 가지면 어떻게 하지? $b_i$를 상수가 아닌 $n$에 대한 다항식으로 두면 아마 될 것 같긴 하다.
3. kitamasa + 빠른 나눗셈
다항식의 곱셈(convolution)이 FFT를 이용해 $O(k\log{k})$만에 가능한 것처럼, 다항식의 나눗셈도 $O(k\log{k})$에 가능하다.
이를 이용해 $a_n$을 $O(k\log{k}\log{n})$만에 구할 수 있다.
ahgus89