키타마사 법
나는 야호다.
오늘은 키타마사법에 대해 배워보도록 하겠다.
선형점화식을 풀자
PS를 하다보면 점화식을 풀 일이 종종 생긴다.
그 중에서 가장 많이 나오는 점화식은 당연히 다음과 같은 선형점화식의 꼴일 것이다.
$$
\begin{aligned}
a_n&=c_1 a_{n-1}+c_2 a_{n-2}+... +c_m a_{n-m}\\
&=\sum c_i a_{n-i}
\end{aligned}
$$
이러한 점화식을 단순하게 푼다면 $$O(mn)$$의 시간복잡도로 해결이 가능하다.
고속행렬 거듭제곱
하지만 $$O(mn)$$으로는 $$n$$이 큰 경우, 예를 들면 10억 쯤되는 $$n$$에 대해서는 계산이 불가능하다.
우리는 이를 해결하기 위해서 위의 점화식을 다음과 같은 행렬식으로 변환할 수 있다.
$$
\begin{pmatrix}a_n\\a_{n-1}\\...\\a_{n-m+1} \end{pmatrix} =
\begin{pmatrix}c_1&...&c_m\\\\&I&0 \end{pmatrix}
\begin{pmatrix}a_{n-1}\\a_{n-2}\\...\\a_{n-m} \end{pmatrix}
$$
이 식을 반복적으로 적용하면 다음과 같은 식을 얻을 수 있다.
$$
\begin{pmatrix}a_n\\a_{n-1}\\...\\a_{n-m+1} \end{pmatrix} =
\begin{pmatrix}c_1&...&c_m\\\\&I&0 \end{pmatrix} ^{m-n}
\begin{pmatrix}a_{m}\\a_{m-1}\\...\\a_{1} \end{pmatrix}
$$
행렬의 거듭제곱은 다음과 같은 분할정복으로 계산할 수 있다.
$$A^n = \begin{cases} A ^ {n/2} * A^{n/2} &\text{if n is even}\\
A ^{n-1}*A &\text{if n is odd} \end{cases}$$
일반적인 행렬곱셈으로 계산한다면 행렬의 크기가 $$m$$ by $$m$$일 때, 시간복잡도를 분석해보면 $$T(n)=T(n/2)+O(m^3)$$이고 마스터 정리에 의해서 $$T(n)=O(m^3 logn)$$가 된다.
키타마사법의 기본 아이디어
키타마사법은 임의의 $$n$$번째 항을 1~$$m$$번 째 항의 선형결합으로 나타내는 것에서부터 시작한다.
$$a_n = d_1 a_1 + d_2 a_2 + ... + d_m a_m =\sum_{\substack{1\leq i \leq m}} d_i a_i$$
조금 생각해보면 선형점화식으로 구해진거라 다음도 성립함을 알 수 있다.
$$a_{n+k} =\sum_{\substack{1\leq i \leq m}} d_i a_{i+k}$$
이 식의 $$k$$에 $$n$$을 대입하면 다음과 같이 정리가 가능하다.
$$
\begin{aligned}
a_{2n}&=a_{n+n}\\
&=\sum_{\substack{1\leq i \leq m}} d_i a_{i+n}\\
&=\sum_{\substack{1\leq i \leq m}} d_i \sum_{\substack{1\leq j \leq m}} d_j a_{i+j}\\
&=\sum_{\substack{1\leq i \leq m\\ 1 \leq j \leq m}} d_i d_j a_{i+j}
\end{aligned}$$
이 식에서 알수 있듯이 우리는 $$a_n$$에 해당하는 $$d_i$$ 값을 알고있다면, 이를 이용하여 $$a_{2n}$$을 $$a_2$$부터 $$a_{2m}$$의 선형결합으로 바꿀수 있다.
그럼 우리는 $$a_n$$을 다음과 같은 방법으로 구할수 있게 된다.
- $$n$$이 짝수라면 위에서 설명한 방법으로 $$a_{n/2}$$의 $$d_i$$를 이용하여 $$a_n$$을 $$a_2$$부터 $$a_{2m}$$의 선형결합으로 바꾼 후, 이를 $$a_{2m}$$부터 차례로 계산해주어 $$a_1$$에서 $$a_m$$의 선형결합으로 바꾼다.
- $$n$$이 홀수라면 $$a_{n-1}$$의 $$d_i$$에서 한단계 계산하여, $$a_n$$의 $$d_i$$를 구한다.
- 위에서 구한 $$d_i$$와 초기항을 가지고 $$a_n$$의 값을 구한다.
1번 과정은 $$T(n)=T(n/2)+O(m^2)$$으로 마스터 정리에 의해 $$O(m ^2 logn)$$의 시간복잡도가 걸린다.
여기선 1번과정이 병목이고 총 시간복잡도는 $$O(m^2logn)$$이다.
코드는 집가서 올림ㅋ 근데 별로안어려움