이번 글에서는 선형 점화식의 $n$번째 항을 빠르게 구하는 방법에 대해 알아보도록 하겠습니다.
문제
다음과 같이 정의되는 무한수열 ${a_n}$이 있습니다.
\[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}\]$n$과 초항 $a_1, a_2, \ldots, a_k$, 계수 $c_1, c_2, \ldots, c_k$ 이 주어지면 $a_n$을 구하는 것이 목표입니다.
가장 간단한 방법부터, 이번 글의 최종 목표인 $O(k log k log n)$ 만에 구하는 방법까지 알아보도록 하겠습니다.
정의를 대입
가장 간단한 방법으로, 점화식 그대로 $a_{k+1}, a_{k+2}, \ldots, a_n$을 순서대로 구하는 방법이 있습니다. 이 방법의 시간복잡도는 $O(nk)$로, 구현이나 생각이 아주 단순한 만큼 효율적인 방법은 아닙니다.
비슷한 방법으로, 점화식을 이용해 $a_n$을 $a_{n-1}, a_{n-2}, \ldots, a_{n-k}$로 표현하고, 다시 $a_{n-1}$을 $a_{n-2}, a_{n-3}, \ldots, a_{n-k-1}$로 표현하는 과정을 반복하여 대입해주면, 최종적으로 $a_n$을 다음과 같은 식으로 표현할 수 있게 됩니다.
\[a_n = d_1 a_1 + d_2 a_2 + \ldots + d_k a_k\]마지막으로 주어진 초항을 대입하면 역시 $O(nk)$ 시간으로 $a_n$을 구할 수 있습니다.
행렬 곱셈
\[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}\] \[a_{n-1} = a_{n-1}\] \[a_{n-2} = a_{n-2}\] \[\vdots\] \[a_{n-k+1} = a_{n-k+1}\]좌변의 $k$개 항이 모두 $a_{n-1}, a_{n-2}, …, a_{n-k}$의 선형 결합으로 표현되므로, 행렬의 곱셈을 이용해 표현할 수 있고, 따라서 행렬의 거듭제곱을 빠르게 계산하여 $a_n$을 계산할 수 있습니다. 행렬 곱셈 한 번에 $O(k^3)$ 시간이 걸리므로, 총 시간복잡도는 $O(k^3 log n)$이 됩니다. 잘 알려져 있는 기법이니 자세한 설명은 생략합니다.
연습문제
키타마사법
위에서 이용한 방법을 다시 관찰해봅시다.
\[a_n = d_1 a_1 + d_2 a_2 + \ldots + d_k a_k\]이 꼴을 만들기 위해 우리가 하는 반복적으로 하는 작업은 점화식을 대입하는 것이고, $a_n$에 $0 = a_n - c_1 a_{n-1} - c_2 a_{n-2} - \ldots - c_k a_{n-k}$ 의 상수배를 더하는 것과 같습니다. 이 과정을 차수가 가장 높은 항부터 반복적으로 적용하여 최고차항의 차수를 계속 낮추어 $k$차 이하의 항만 남게 만들면, 우리가 아는 초항을 대입해 $a_n$을 구할 수 있습니다.
이 과정의 계수 변화를 관찰해보면, 다항식의 나눗셈 과 완벽하게 동일하다는 것을 알 수 있습니다.
$x^n$이라는 다항식을 $f(x) = x^k - c_1 x^{k-1} - c_2 x^{k-2} - \ldots - c^k x^0$로 나눗셈을 하면, 우리가 구하고 싶은 계수들인 $d_1, d_2, \ldots, d_k$는 $x^n$을 $f(x)$로 나눈 나머지인 다항식의 계수에 해당합니다.
따라서 우리가 결국 해야하는 건 $x^n$를 $mod$ $f(x)$ 상에서 계산하는 것이고, 다항식의 곱셈, 나눗셈을 $O(log n)$ 번 하게 됩니다. 곱셈과 나눗셈을 단순하게 $O(k^2)$로 구현하면, $a_n$을 구하는 데 $O(k^2 log n)$ 시간 만에 구할 수 있게 됩니다.
연습문제 (스포 주의)
BOJ 10730 업적의 노예 2 - $a_n$을 구하는 형태는 아니지만, 결국 위에서 설명한 내용으로 구해지는 형태임을 쉽게 관찰할 수 있습니다.
BOJ 18539 Basis Change - 충분히 큰 적당한 $n$을 잡고, $x^n$을 $f(x)$로 나누는데, $x^0, x^1, \ldots, x^{k-1}$을 남기는 것이 아니라 $x^{n-b_1}, x^{n-b_2}, \ldots, x^{n-b_k}$를 남기는 형태입니다. 역시 위의 내용을 이용해야 하고, Gaussian Elimination을 이용하여 답을 구할 수 있습니다.
다항식의 나눗셈
우리는 $k$차 다항식의 곱셈을 FFT를 이용하여 $O(klogk)$ 만에 할 수 있음을 잘 알고 있습니다. 나눗셈 역시 더 빠르게 계산할 수 있다면 전체 시간복잡도도 향상시킬 수 있을 것입니다. 다항식 나눗셈을 빠르게 하는 방법을 알아봅시다.
$n$차 다항식 $a(x)$를 $m$차 다항식 $b(x)$로 나누어 다음과 같이 표현됩니다.
\[a(x) = b(x)q(x) + r(x), deg r < m\]우리는 이러한 $q(x)$나 $r(x)$를 빠르게 찾는 것이 목표입니다. $n \geq m$인 경우만 생각하면, $q(x)$는 $n-m$차 다항식이고, $r(x)$는 $m-1$차 (이하) 다항식입니다.
위 식은 항등식이므로, $x$ 대신 ${1 \over x}$ 를 대입해도 성립합니다.
\[a({1 \over x}) = b({1 \over x}) q({1 \over x}) + r({1 \over x})\]양변을 다항식으로 만들어주기 위해 양변에 $x^n$을 곱해주면 다음과 같습니다.
\[x^n a({1 \over x}) = x^m b({1 \over x}) \cdot x^{n-m} q({1 \over x}) + x^{m-1} r({1 \over x}) \cdot x^{n-m+1}\]일반적으로, $n$차 다항식 $f(x)$에 대해 $x^n f({1 \over x})$는 $f(x)$의 계수 순서를 반대로 뒤집은 다항식이 됩니다. 이런 다항식을 대문자로 표시하면 다음과 같습니다.
\[A(x) = B(x)Q(x) + R(x) \cdot x^{n-m+1}\]$R(x)$는 $n-m$차 다항식이므로, $mod \space x^{n-m+1}$ 상에서 계산해도 정확한 값을 얻을 수 있습니다.
\[A(x) \equiv B(x)Q(x) (mod \space x^{n-m+1})\]우리가 $Q(x)$를 구하기 위해서는 $(mod \space x^{n-m+1})$ 상에서의 $B(x)$의 역원을 찾아 $A(x)$에 곱해주면 됩니다.
그러면 이런 $B(x)$의 역원 $B^{-1} (x)$이 항상 존재하고, 효율적으로 구할 수 있을까요? 그렇습니다.
$mod \space x^{n-m+1}$ 상에서의 계산은 어려우니 $mod \space x$에서 시작해봅시다.
$B(x) B^{-1} (x) \equiv 1 (mod \space x)$인 $B^{-1} (x)$은 어떤가요? $B(x)$의 상수항은 $b(x)$의 최고차항의 계수와 같으므로, 0이 아님이 분명합니다. 따라서 $B^{-1} (x) \equiv (B(x)의 \space 상수항)^{-1} (mod \space x)$가 됩니다.
$B(x)C(x) \equiv 1 (mod \space x^k)$인 $C(x)$를 알고 있다고 가정합시다. 자명하게 다음이 성립합니다.
\[B(x)C(x)-1 \equiv 0 (mod \space x^k)\]양번을 제곱하면 다음과 같습니다.
\[(B(x)C(x)-1)^2 \equiv 0 (mod \space x^{2k})\]전개하고 정리하면 다음과 같은 식을 얻을 수 있습니다.
\[B(x) \cdot C(x)(2-B(x)C(x)) \equiv 1 (mod \space x^{2k})\]따라서 $(mod \space x^{2k})$ 상에서의 역원은 $C(x)(2-B(x)C(x))$임을 알 수 있습니다.
따라서 $mod \space x^k$에서의 역원을 알면 $mod \space x^{2k}$에서의 역원을 $k$차 다항식의 곱셈 두번으로 알 수 있으므로, 이 과정을 반복해 $mod x^{n-m+1}$까지 끌어올리면 됩니다. 일반적으로 $n-m+1$이 항상 $2$의 거듭제곱은 아니니 $n-m+1$보다 큰 $2$의 거듭제곱까지 계산하면 충분합니다.
$k$차식의 나눗셈에 걸리는 시간을 $T(k)$라 하면, $mod \space x$에서의 역원은 $O(1)$만에 알 수 있으므로 $T(k) = T({k \over 2}) + O(m(k)) $ 가 되고, $T(k) = O(m(k))$가 됩니다. 이때 $m(k)$는 다항식의 곱셈에 걸리는 시간으로, FFT를 사용하여 $O(klogk)$만에 할 수 있습니다.
따라서 위의 과정을 이용해 $B^{-1} (x)$를 구하고, $A(x)$에 곱하고, 차수가 $n-m$ 이하인 항만 취한 뒤 계수 순서를 다시 뒤집어주면 $q(x)$를 구해낼 수 있습니다.
이렇게 구현된 $O(klogk)$ 다항식 곱셈/나눗셈을 통해 키타마사법을 구현하면, $a_n$을 $O(klogklogn)$ 시간에 구할 수 있습니다. FFT를 이용한 다항식 곱셈 부분만 복붙 등으로 해결한다면, 나눗셈이나 키타마사법 등은 쉽게 구현할 수 있습니다.
연습문제
BOJ 13725 RNG 위에서 설명한 내용을 그대로 구현하면 됩니다.
BOJ 13178 목공 점화식을 세우면, 선형점화식인 듯 하지만 상수항이 거슬리는 형태입니다. 상수항을 제외한 나눗셈 과정에서 상수항이 미치는 영향을 관찰하면 풀 수 있습니다.