선형 점화식 - Linear Recurrence Relation
선형 점화식이란 다음과 같이 상수 계수를 가진 몇 개의 항의 선형 결합으로 구성된 점화식을 말한다.
\[a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ma_{n-m}\]이미 계수가 결정되어있을 때 $n$번째 항을 계산하는 방법은 다양한데, naive하게 구현하면 $O(nm)$이 걸리고, 행렬곱을 이용하면 $O(m^3log(n))$에 구할 수 있다. 관련 내용은 여기를 참고하자.
키타마사법 - Kitamasa Method
정의
앞서 설명한 방법보다 훨씬 빠르게 선형 점화식과 n, 그리고 초항과 계수가 주어졌을 때 $n$번째 항을 $O(m^2log(n))$에 구할 수 있는 알고리즘이다.
많은 자료들을 탐색해 본 결과 $a_n$을 $a_{2n}$으로 바꾸는 방법과 다항식의 나눗셈을 이용한 방법을 찾아볼 수 있었다. 아직 부족한 지식으로 인하여 연관성은 찾지 못하였지만 일단 두 방법 모두 소개하고자 한다.
혹시 틀린부분이나 공통점 혹은 차이점을 알고 계시는 분은 댓글로 알려주시면 정말 감사하겠습니다!
$a_{2n}$ 과 $a_n$
아이디어
이 알고리즘의 핵심 아이디어는 모든 항은 $a_n=\sum_{k=1}^ma_kd_k$ 꼴로 변형될 수 있다는 것이다. 이를 행렬곱과 연관지어 보면
\[\begin{pmatrix} a_n\\ a_{n-1}\\ \vdots\\ a_{n-m+1} \end{pmatrix} = \begin{pmatrix} c_1&c_2&\cdots&c_m\\ 1&0&\cdots&0\\ \vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&0 \end{pmatrix} \cdot \begin{pmatrix} a_{n-1}\\ a_{n-2}\\ \vdots\\ a_{n-m} \end{pmatrix}\] \[\Leftrightarrow v_n=M\cdot v_{n-1}\]이 형태를 잘 관찰해보면 결국 행렬의 거듭제곱으로 $n$번째 항을 구하게 되므로 $v_n=M^{n-m}v_m$ 에서 임의의 자연수 $h$에 대해서 $v_{n+h}=M^{n-m}v_{m+h}$가 성립함을 알 수 있다.
즉 $a_n=\sum_{k=1}^ma_kd_k$에서 $a_{n+h}=\sum_{k=1}^ma_{k+h}d_k$가 성립함을 알 수 있다!
여기서 $h$에 $n$을 대입하면 $a_{2n}=\sum_{k=1}^ma_{n+k}d_k=\sum_{k=1}^m\sum_{j=1}^ma_{j+k}d_jd_k$ 가 성립한다.
따라서, $a_{2n}$을 $a_1,a_2,\cdots,a_{2m}$으로 표현할 수 있고, 계수는 $O(m^2)$ 안에 구할 수 있다.
또한 $a_{m+1},a_{m+2},\cdots,a_{2m}$을 $a_1,a_2,\cdots,a_m$으로 $O(m^2)$으로 표현할 수 있다.
이로써 $a_n$에 대한 식을 $a_{2n}$에 대한 식으로 변형하는데 $O(m^2)$ 밖에 걸리지 않게 되어 $O(m^2log(n))$ 안에 $n$번째 항을 계산할 수 있다.
구현
구현은 cubelover님의 블로그를 참고하자.
다항식의 나눗셈
아이디어
이 알고리즘의 핵심 아이디어는 점화식을 변형하는 과정이 다항식의 나눗셈을 하는 과정과 일치하다는 것이다.
\[a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ma_{n-m}\]에서 $k$개의 초항으로 구성된 점화식의 꼴로 변형하기 위해 $0=a_n-c_1a_{n-1}-c_2a_{n-2}-\cdots-c_ma_{n-m}$을 반복해서 빼준다.
\[a_n-0=(c_1a_{n-1}+\cdots)-c_1(a_{n-1}-c_1a_{n-2}+\cdots)\]이후 최종적으로는 $m$개의 항이 남게 되는데, 이때 $a_k$를 $x^k$에 대응시켜보자. 그러면 이 과정은 $x^n$을 $f(x)=x^m-\sum_{i=1}^{m}c_ix^{n-i}$ 으로 나누는 과정과 신기하게 일치한다! 따라서 나눈 나머지의 계수가 $m$개의 초항의 계수가 된다.
빠른 나눗셈
먼저 이를 위해서는 다항식의 빠른 나눗셈이 필요하다. 이는 FFT를 활용하면 되는데, 식 정리를 잘 해보면 곱셈과 덧셈만으로도 나눗셈을 구현할 수 있다!
$n$차 다항식 $a(x)$를 $m$차 다항식 $b(x)$로 나누면 다음과 같다.
\[a(x)=b(x)q(x)+r(x)\]이때, $q(x)$는 $n-m$차, $r(x)$는 $m-1$차 다항식이다.
위 식은 항등식이므로 $x$ 대신 $\cfrac{1}{x}$을 대입해도 성립하고,
\[a(\cfrac{1}{x})=b(\cfrac{1}{x})q(\cfrac{1}{x})+r(\cfrac{1}{x})\]양변에 $x^n$을 곱해줘도 성립한다.
\[x^na(\cfrac{1}{x})=x^mb(\cfrac{1}{x})x^{n-m}q(\cfrac{1}{x})+x^{m-1}r(\cfrac{1}{x})x^{n-m+1}\]이때, $n$차 다항식 $f(x)$에 대해서 $\cfrac{1}{x}$를 대입하고 다시 $x^n$을 곱해주면 계수가 거꾸로된 다항식이 됨은 자명하다.
따라서 위 식을 다시 정리하여 다음과 같이 나타낼 수 있다.
\[A(x)=B(x)Q(x)+R(x)x^{n-m+1}\]이를 합동식의 형태로 바꾸면
\[A(x)\equiv B(x)Q(x)\ (mod\ x^{n-m+1})\]가 된다. 이때, $B(x)$의 역원을 찾아 양변에 곱해주면
\[A(x)B^{-1}(x)\equiv Q(x)\ (mod\ x^{n-m+1})\]가 된다. 이제 $B(x)$의 역원을 찾아보자.
base 케이스인 $mod\ x$인 경우에는 상수항의 역수가 됨은 자명하다.
그러면 $mod\ x^k$에서의 역원을 알고 있을 때, $mod\ x^{2k}$를 구할 수 있는 방법을 생각해보자.
$B(x)B^{-1}(x)-1\equiv 0\ (mod\ x^k)$ 일때, 좌변의 식은 $x^k$를 인수로 가지고 있으므로 양변을 제곱했을 때 다음이 성립한다.
\[(B(x)B^{-1}(x)-1)^2\equiv 0\ (mod\ x^{2k})\]식을 정리하면
\[B(x)B^{-1}(x)(2-B(x)B^{-1}(x))\equiv 1\ (mod\ x^{2k})\]이므로 $mod\ x^{2k}$에서의 역원은 $B^{-1}(x)(2-B(x)B^{-1}(x))$임을 알 수 있다.
따라서 역원을 구한 뒤, 다시 $A(x)$에 역원을 곱하고, $n-m$ 이하의 차수만 뽑아내서 계수를 뒤집어주면 된다.
구현
빠른 다항식 곱셈은 FFT의 경우 시간복잡도에서 상수의 크기 때문에 NTT를 사용해서 구현을 해주어야 한다. 이것 때문에 정말 많이 고생했다..
위 내용들을 그대로 구현하는 RNG 문제를 풀어보는 것을 추천한다.
벡터 복사나 함수 인자로 넘겨주는 부분만 잘 생각해서 구현 해준다면 쉽게 통과할 수 있을 것이다!
참고문헌
- https://tamref.com/30
- https://cubelover.tistory.com/21
- https://koosaga.com/231
- https://justicehui.github.io/hard-algorithm/2021/03/13/kitamasa/
- https://algoshitpo.github.io/2020/05/20/linear-recurrence/
- https://infossm.github.io/blog/2019/04/10/polynomial-division