티스토리 뷰

공부

Bostan Mori 알고리즘

전명우 2022. 11. 30. 15:53

Bostan Mori 알고리즘은 2020년 8월 Alin Bostan과 Ryuhei Mori가 작성한 이 논문에 소개되어 있는 선형점화식을 가지는 수열의 $N$ 번째 항을 빠르게 구하는 알고리즘이다. Bostan Mori 알고리즘 이외에 선형점화식을 가지는 수열의 $N$ 번째 항을 빠르게 구하는 방법은 이 글을 참고하자.

 

$D_0, D_1, \cdots, D_{k-1}$과 $c_1, c_2, \cdots, c_k$가 주어졌을 때, $i \ge k$인 $D_i$를 다음과 같은 선형점화식으로 구할 수 있다고 하자.

$$D_i = \sum_{j=1}^{k}{c_jD_{i-j}} = c_1D_{i-1} + c_2D_{i-2} + \cdots + c_kD_{i-k}$$

이러한 선형점화식이 주어졌을 때, $D_N$을 Bostan Mori 알고리즘을 통해 구하는 방법을 알아보자.

 

$D$의 각 원소를 계수로 가지는 생성함수 $F$와 점화식을 바탕으로 만들어진 다항함수 $Q$가 있다.

$$F(x) = \sum_{n=0}^{\infty}{D_nx^n}\\Q(x) = 1-c_1x-c_2x^2-\cdots-c_kx^k$$

여기서, $F(x) = \frac{P(x)}{Q(x)}$를 만족하는 다항함수 $P$가 존재한다는 것과 $P$의 차수가 $k$ 보다 작다는 것을 보일 수 있다. $P(x) = F(x)Q(x)$이고, $i \ge k$인 $i$에 대해 $P(x)$의 $x^i$ 항의 계수를 구해보면 $D_i - c_1D_{i-1} - c_2D_{i-2} - \cdots - c_kD_{i-k} = 0$이다. 즉, $P(x)$의 차수는 $k$ 보다 작다.

 

구하고자 하는 것은 $N$ 번째 항인 $D_N$이다. 이는 $F(x) = \frac{P(x)}{Q(x)}$의 $x^N$ 항의 계수이다. 이를 다음과 같은 수식으로 표현하자.

$$\left[x^N\right]\frac{P(x)}{Q(x)}$$

위 분수의 분자와 분모 모두에 $Q(-x)$를 곱해보자. 즉, $\frac{P(x)}{Q(x)} = \frac{P(x)Q(-x)}{Q(x)Q(-x)}$이다.

이때, $Q(x)$의 차수는 $k$이다. $Q(x)Q(-x)$는 짝함수이기 때문에 $V(x^2)$으로 나타낼 수 있으며 $V$의 차수는 $k$ 이하다. $P(x)Q(-x) = U(x)$로 쓰자. $P(x)$의 차수는 $k$ 보다 작기 때문에 $U(x)$의 차수는 $2k$ 보다 작다. $U(x)$를 홀수차항과 짝수차항으로 $U(x) = U_e(x^2) + xU_o(x^2)$처럼 나누자. 여기서 $U_e(x)$와 $U_o(x)$의 차수는 $k$ 보다 작다. 이를 통해 식을 다음처럼 정리할 수 있다.

$$\frac{P(x)}{Q(x)} = \frac{P(x)Q(-x)}{Q(x)Q(-x)} = \frac{U_e(x^2)}{V(x^2)} + x\frac{U_o(x^2)}{V(x^2)}$$

유리함수 $P/Q$의 $x^N$ 항의 계수는 다음과 같이 정리된다.

$$\left[ x^N \right]\frac{P(x)}{Q(x)} = \begin{cases}
\left[ x^{\frac{N}{2}} \right] \frac{U_e(x)}{V(x)}, & \text{if $N$ is even,}\\
\left[ x^{\frac{N-1}{2}} \right] \frac{U_o(x)}{V(x)}, & \text{otherwise}
 \end{cases}$$

즉, 분자의 차수가 $k$보다 작고, 분모의 차수가 $k$ 이하인 유리함수 $P/Q$의 $x^N$ 항의 계수를 구하기 위해 같은 조건을 가지고 있는 또다른 유리함수의 $x^{\lfloor N/2 \rfloor}$의 계수를 구하도록 차원을 줄였다. 이처럼 두 번의 다항식 곱셈으로 구하고자 하는 항의 차수를 반으로 줄일 수 있다. 이를 상수항의 계수를 구할 때까지 반복한다. 유리함수 $P/Q$의 상수 계수는 $P(0)/Q(0)$으로 바로 구할 수 있다.

 

일반적인 방법으로 다항식의 곱셈을 구현하면 $O(k^2)$ 시간복잡도가 되고, FFT나 NTT를 통해 다항식의 곱셈을 구현하면 $O(k \lg k)$ 시간복잡도가 된다. 따라서, 전체 시간복잡도는 $O(k^2 \lg N)$ 혹은 $O(k \lg k \lg N)$이다.

 

연습 문제

https://boj.kr/15572

문제의 MOD 값이 1999이므로 NTT를 사용할 수 없다. $k$의 최댓값이 1000으로 크지 않으므로 $O(k^2 \lg N)$ 시간복잡도로 해결할 수 있다.

 

15572번: 블록 4

여러 가지 블록들을 이용하여 직사각형 모양을 만들려고 한다. 우리에게는 1 × N 블록, 2 × N 블록, ..., N × N 블록이 무한하게 있다. 이 블록들을 사용하여 N × M 모양을 만들고

www.acmicpc.net

https://boj.kr/13725

MOD 값이 $104857601 = 25 \times 2^{22}+1$ 로 NTT를 쓸 수 있다. 원시근은 2부터 차례대로 구해보면 되는데, 3이 원시근이 된다. $k$의 최댓값이 30000으로 크기 때문에 $O(k \lg k \lg N)$ 시간복잡도로 문제를 해결해야 한다.

 

13725번: RNG

첫째 줄에 k와 N (1 ≤ k ≤ 30,000, 1 ≤ N ≤ 1018)이 주어진다. 둘째 줄에는 A1, A2, ..., Ak가 셋째 줄에는 C1, C2, ..., Ck가 주어진다. (0 ≤ Ai, Ci < 104857601)

www.acmicpc.net

아래 코드는 BOJ 13725 RNG 문제를 해결하는 코드이며, mod int와 NTT를 이용한 다항식 템플릿을 포함한 코드다.

더보기

'공부' 카테고리의 다른 글

선형점화식 빠르게 계산하기  (0) 2022.11.30
다항식 나눗셈의 몫을 빠르게 구하는 방법  (0) 2022.11.29
Hu-Tucker Algorithm  (0) 2022.05.03
Skew Heap  (0) 2022.05.03
Z-function  (2) 2021.03.08
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2023/09   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함