다항식 연산들로 할 수 있는 것

2022-10-15) 미완성이지만 일단 초안을 업로드했습니다. 계속 내용 수정중에 있습니다.

 

2022-11-16) 부족한 부분들을 많이 채워넣었습니다. Shift of Sampling Points of Polynomial이외의 모든 내용을 넣었으며, 추후 다른 토픽들을 더 추가할 예정입니다. 또한 각 토픽에 대한 연습문제 링크를 첨부하려고 합니다.

 

이전 글이 너무 길어질것 같아서 다항식 연산의 응용문제들을 따로 뺐습니다.

이 글에서는 다음 문제들을 다룰것입니다.

 

0. 목차

1. Polynomial Taylor Shift $ \mathcal{O}(T \log T) $

2. #p Subset Sum $ \mathcal{O}(T \log T) $

3. Partition Number 계산 $ \mathcal{O}(T \log T) $

4. 다항식 $f$가 주어졌을때, $f(x)^k$ mod $ 1 - x^T$ 계산하기 $ \mathcal{O}(T \log T + T \log k) $

5. 다항식 $f,g$가 주어졌을때 $f/g$의 초기 $T$개의 항 계산하기 $ \mathcal{O}(T \log T) $

6. 다항식 $f,g$가 주어졌을때 $f/g$의 $N$번째 항 계산하기 $ \mathcal{O}(k \log k \log N) $

7. C-Recursive Sequence $ \mathcal{O}(k^2 + T \log T), \mathcal{O}(k^2 + k \log k \log N) $

8. 유리식들의 합 $\mathcal{O}(T \log^2 T)$

9. $ \sum_{i=1}^n a_i^j$를 $T$미만의 모든 $j$에 대해서 계산 $\mathcal{O}(T \log^2 T)$

10. $f(x) f(rx) f(r^2) \cdots f(r^{n-1} x) $의 계산 $\mathcal{O}(T \log T)$

11. 초기 $T$개의 Bell 수 $\mathcal{O}(T \log T)$

12. 제 1종 스털링 수 $\mathcal{O}(n \log n)$

13. 제 2종 스털링 수 $\mathcal{O}(n \log n)$

14. $ \sum_{i=0}^n A_i (x+a)^i (x+b)^{T-i} $의 계산 $ \mathcal{O}(T \log T) $

15. Multipoint Evaluation  $ \mathcal{O}(n \log^2 n) $

16. Lagrange Interpolation $ \mathcal{O}(n \log^2 n) $

(미완) 17. Shift of Sampling Points of Polynomial

18. $\sum_{n=0}^N n^k$ 를 $T$미만의 모든 $k$에 대해서 계산 $ \mathcal{O}(T \log T) $

19. 초기 $T$개의 베르누이 수 $ \mathcal{O}(T \log T) $

20. $\sum_{n=0}^N n^k r^n , \sum_{n=0}^\infty n^k r^n $의 계산 $\mathcal{O}(k \log k \log N)$

21. $\sum_{k=L}^{R} f(kx)$의 첫 $T$개의 항 계산 $\mathcal{O}(T \log T)$

22. $\prod_{k=L}^{R} f(kx)$의 계산

23. relaxed multiplication

24. $\prod_{i=1}^N (a_i x + b_i)^{c_i} $의 첫 $T$개의 항 $\mathcal{O}(N \log^2 N + T \log T)$

25. $\sum_{i=1}^N a_i e^{b_i x}$ 의 첫 $T$개의 항 계산 $\mathcal{O}(N \log^2 N + T \log T)$

 

1. Polynomial Taylor Shift $ \mathcal{O}(T \log T) $

 

Polynomial Taylor Shift란 다항식 $f(x)$가 주어졌을때, 다항식 $f(x+c)$를 계산하는 방법을 말합니다. 즉, 만약 $f(x) = a_0 + a_1 x + \cdots + a_{T-1} x^{T-1}$라고 할때, $f(x+c) = b_0 + b_1 x + \cdots + b_{T-1} x^{T-1}$ 가 되게하는 $b$를 구하는 방법을 말합니다. 단순히 FFT를 응용하면 되지않나? 싶을 수 있지만 그러기 위해선 $T$개의 점들에 대해서 $f$값을 알아야 하고, 이걸 계산하는 것자체가 $T^2$이기 때문에 FFT를 쓰는 의미가 없습니다.

 

$f(x) = \sum_{k=0}^{T-1} \frac{A_k}{k!} x^k$로 정의하면,

\[ \begin{align} f(x+c) &= \sum_{k=0}^{T-1} \frac{A_k}{k!} (x+c)^k \\ &= \sum_{k=0}^{T-1} \sum_{i=0}^{k} \frac{A_k}{k!} \binom ki c^{k-i} x^i \\ &= \sum_{k=0}^{T-1} \sum_{i=0}^k A_k \frac{c^{k-i}}{(k-i)!} \frac{x^i}{i!} \\ &= \sum_{i=0}^{T-1} \sum_{k=i}^{T-1} A_k \frac{c^{k-i}}{(k-i)!} \frac{x^i}{i!} \\ &= \sum_{i=0}^{T-1} B_i \frac{x^i}{i!}, B_i = \sum_{k=i}^{T-1} A_k \frac{c^{k-i}}{(k-i)!}  \end{align} \]

 

여기서, $B_0, B_1, \cdots, B_{T-1}$의 값들은 FFT를 이용하면 $ \mathcal{O}(T \log T) $에 계산이 가능하므로, $f(x+c)$역시 $ \mathcal{O}(T \log T) $에 계산이 가능하게 됩니다.

 

2. #p Subset Sum $ \mathcal{O}(T \log T) $

 

$1 \leq a_i \leq T-1$를 만족하는 수열 $a_1, a_2, \cdots, a_N$에 대하여, $a_{i_1} + a_{i_2} + \cdots + a_{i_k} = s$가 되게 하는 부분집합 {$i_1, i_2, \cdots, i_k$}의 개수를 $b_s$라고 정의할때, $b_0, b_1, \cdots b_{T-1}$를 구하는 문제입니다. 간단한 관찰로 다음과 같은 사실을 알 수 있습니다.

 

$ b_0 + b_1x + \cdots + b_{T-1} x^{T-1} = (1+x^{a_1})(1+x^{a_2})\cdots(1+x^{a_{N}})$ mod $ x^T $

 

그래서 오른쪽 다항식만 곱할줄만 알면 되기에 쉬워보이는것처럼 보이나, 오른쪽 다항식을 정의하는데만 $ \mathcal{O}(TN) $의 연산이 필요하기 때문에, 다항식을 정의하는것 만으로도 시간초과를 받게됩니다.

 

식을 다음과 같이 정리합니다.

 

\[ \begin{align} (1+x^{a_1})(1+x^{a_2})\cdots(1+x^{a_{N}}) &= e^{ \log (1+x^{a_1})(1+x^{a_2})\cdots(1+x^{a_{N}})} \\ &= e^{ \sum_{i=1}^{N} \log(1+x^{a_i}) } \\ &= e^{ \sum_{i=1}^N (x^{a_i} - \frac{1}{2} x^{2 a_i} + \frac{1}{3} x^{3 a_i} - \frac{1}{4} x^{4 a_i} + \cdots) } \end{align} \]

 

각 $a_i$마다 지수안에 다항식을 정의하는데 드는 연산은 총 $ T / a_i $ 므로, $a_i$들이 중복되는 개수를 미리 세는것으로 중복을 제거하였다고 가정하면, 지수안에 다항식을 정의하는데 연산은 최대 $ \frac{T}{1} + \frac{T}{2} + \cdots $가 되게 됩니다. Harmonic Series를 생각하면 이 값은 $ \mathcal{O}(T \log T) $므로, $ \mathcal{O}(T \log T) $ 시간으로 $ \sum (x^{a_i} - \frac{1}{2} x^{2 a_i} + \cdots) $ 를 계산할 수 있습니다. 이 exp 함수로 정의된 값은 6. 방법을 이용하면 $ \mathcal{O}(T \log T) $에 계산이 가능하므로, 총 $ \mathcal{O}(T \log T) $의 시간에 #p Subset Sum 문제를 풀 수 있게 됩니다.

 

3. Partition Number 계산 $ \mathcal{O}(T \log T) $

 

$b_s$를 $s$의 partition number, 즉 $s$를 서로 다른 자연수의 합으로 표현하는 방법의 수라고 정의합시다. 위의 #p Subset Sum 문제와 다르게, 중복을 세지 않습니다. 예를 들어, 위의 #p Subset Sum은 $a$가 주어지는것에 따라 $3 = 1+2, 3 = 2+1$을 전부 세게 될 수도 있지만, partition number는 $3=1+2$로 표현했으면 $3=2+1$은 세지 않습니다. 자세한 partition number의 정의는 위키피디아를 참고해주세요.

https://en.wikipedia.org/wiki/Partition_(number_theory) 

 

Partition number의 초기 $T$개항 $b_0, b_1, \cdots, b_{T-1}$을 계산하려고 합니다. Pentagonal Number Theorem에 의하여 다음이 성립합니다.

 

\[ \sum_{i=0}^\infty b_i x^i = \prod_{k=1}^{\infty} (1-x^k)^{-1} \]

 

초기 $T$개의 항을 볼것이고, #p Subset Sum에서 사용한 아이디어를 그대로 사용하면 다음과 같이 됩니다.

 

\[ \sum_{i=0}^{T-1} b_i x^i = \prod_{k=1}^{T-1} (1-x^k)^{-1} \text{ mod } x^T \]

 

이 식의 값을 구하는 방법은 #p Subset Sum에서 사용한 아이디어와 완전히 같으므로 자세한 설명은 생략합니다.

 

예제: https://judge.yosupo.jp/problem/partition_function

 

4. 다항식 $f$가 주어졌을때, $f(x)^k$ mod $ 1 - x^T$ 계산하기 $ \mathcal{O}(T \log T + T \log k) $

 

다항식 $f$가 주어졌을때, $f(x)^k$ mod $ 1 - x^T$를 계산하는 방법입니다. 이전에 저희는 다항식 $f,g$가 주어졌을때 $f$를 $g$로 나눈 나머지를 $ \mathcal{O}(T \log T) $에 계산하는 방법에 대해서 배웠습니다. 그러므로, $f$ mod $1 - x^T$를 계산 한뒤, 이 다항식을 $k$ 거듭제곱 해주면 됩니다. $\log$를 취하고 $e^f$를 계산하는 방법은 $x^T$이후의 항을 전부 날려버리는 계산이기 때문에, 여기서 사용은 못하고, 일반적인 숫자 거듭제곱을 해주듯이 하면 됩니다. 그러면 $ \mathcal{O}(T \log T \log k) $에 계산이 가능합니다. 하지만, 만약 $T$가 2의 거듭제곱꼴이라면 더 빠르게 하는 방법이 존재합니다. 그리고 그 방법을 Chirp Z-Transform이라고 부릅니다.

 

방법은 어렵지 않습니다만, FFT에 대한 이해를 하고 있어야 합니다. FFT의 원리를 간단하게 상기해보면, 다항식 $f$가 주어졌을때 원시근을 이용하여 $f(1), f(w), f(w^2) , \cdots, f(w^{T-1})$을 $\mathcal{O}(T \log T)$에 계산을 했습니다. 그리고 적당한 연산 뒤에 FFT 역변환을 취해주면 저희가 원하는 결과를 얻을 수 있었습니다. Chirp Z-Transform은 이 중간과정에서 $f(1), f(w), f(w^2) , \cdots, f(w^{T-1})$를 $k$제곱하여 $f(1)^k, f(w)^k, f(w^2)^k, \cdots, f(w^{T-1})^k$를 계산한뒤 이 값을 FFT 역변환 해주면 됩니다. FFT가 $\mathcal{O}(T \log T)$, 그리고 $T$개의 숫자를 $k$제곱하는데 $\mathcal{O}(T \log k)$가 소모되므로, 총 $ \mathcal{O}(T \log T + T \log k) $의 연산으로 $f(x)^k$ mod $ 1 - x^T $ 를 계산할 수 있습니다.

 

5. 다항식 $f,g$가 주어졌을때 $f/g$의 초기 $T$개의 항 계산하기 $ \mathcal{O}(T \log T) $

 

다항식 나눗셈을 하는 법에 대해서 배웠으니 그것을 그대로 사용하면 됩니다. 자세한 설명은 생략합니다.

그런데 이건 지금까지 계속 언급한 Ring $ Z_p[x] \text{ mod } x^T $ 위에서 생각했을때 계산할 수 있다는 것이지 만약 $T$값과 관련없이 $f/g$의 $N$번째 항을 계산하고 싶다고 한다면 특수한 방법이 필요한데 그것이...

 

6. 다항식 $f,g$가 주어졌을때 $f/g$의 $N$번째 항 계산하기 $ \mathcal{O}(k \log k \log N) $

 

Bostan-Mori라고 하는 방법입니다.여기서 $N$은 아주 크다고 가정하고, 분모에 해당하는 다항식 $f,g$의 차수가 $k$이하라고 가정합니다. 이경우, $N$이 너무나도 커서 5. 방법을 그대로 사용하기 못하기에 특수한 방법을 사용해야합니다.

 

먼저, 적당한 $T$값을 정합니다. 주로 $T=1$로 설정하여 상수부분만 봅니다. 이때, 다음 방법을 $N$이 $T$미만이 될때까지 반복합니다.

1) $u(x) = f(x) \times g(-x), v(x) = g(x) \times g(-x)$로 정의합니다. 이때, $g(-x)$는 $g(x)$의 홀수차항에 전부 -1을 곱한 다항식입니다. $u,v$의 계산에 $\mathcal{O}(k \log k)$가 소요됩니다.

 

2) FFT에서 했던것처럼, $u(x),v(x)$를 다음과 같이 분해합니다.

\[ u(x) = x u_{odd}(x^2) + u_{even}(x^2), v(x) = x v_{odd}(x^2) + v_{even}(x^2) \]

 

이때, $v(x) = g(x) \times g(-x)$로 정의하였기에 홀수차항이 전부 상쇄되어 없다는걸 알 수 있습니다. 즉, $v_{odd}(x) = 0$이 성립합니다.

 

3) 다음이 성립합니다.

 

수식 적기 귀찮아서 다른 글에서 수식을 가져옵니다. 출처: https://www.secmem.org/blog/2021/12/21/Bostan-Mori_Algorithm/

 

4) $N$이 $T$미만이 되었다면 5.에서 정의된 방법을 사용하고, 그것이 아니라면 1)로 되돌아가서 다시 $N$의 차수를 반으로 줄여주는 과정을 반복합니다. $u_{odd}, u_{even}, v_{even}$ 역시 차수가 $k$이하가 되므로 초기조건과 완전히 일치하는 것을 알 수 있습니다. 즉, 과정을 반복하는데 문제없습니다.

 

한번 iteration을 할때마다 $\mathcal{O}(k \log k)$가 소모되며,  총 $\log N$번 반복하므로, 전체 시간은 $\mathcal{O}(k \log k \log N)$이 됩니다.

 

7. C-Recursive Sequence $ \mathcal{O}(k^2 + T \log T), \mathcal{O}(k^2 + k \log k \log N) $

 

적당한 정수 $k$와 수열 $c_1, c_2, \cdots, c_k$와 초기항 $a_0, a_1, \cdots, a_{k-1}$가 주어졌을때, 다음과 같은 형태로 재귀적으로 주어진 수열을 C-Recursive Sequence라고 정의합니다.

 

\[ a_i = c_1 a_{i-1} + c_2 a_{i-2} + \cdots + c_k a_{i-k} \text{ for all } i \geq k \]

 

가장 대표적인 C-Recursive Sequence로는 피보나치 수열이 존재합니다. $k=2$로 설정하고 $c_1 = c_2 = 1$, $a_0 = a_1 = 1$로 정의하면 되기 때문입니다. C-Recursive Sequence의 $N$번째 항은 행렬 거듭제곱을 이용하여 $ \mathcal{O}(k^3 \log N) $만에 구할 수 있는것이 알려져 있습니다(잘 모르겠다면, $N$번째 피보나치 숫자를 어떻게 구했었는지 생각해보세요). 실제 PS에서도 이 방법만 알고 있어도 거의 모든 문제를 풀 수 있습니다만, 다항식 연산들을 이용하면 더 빠르게 계산하는것이 가능합니다.

 

다음 식을 생각해봅시다.

 

\[ (a_0 + a_1 x + a_2 x^2 + \cdots) ( 1 - c_1 x - c_2 x^2 - \cdots - c_{k} x^k) = b_0 + b_1 x + b_2 x^2 + \cdots \]

 

$ i \geq k $ 라고 가정하면, $ b_i = a_i - c_1 a_{i-1} - c_2 a_{i-2} - \cdots - c_k a_{i-k} $가 되고, 이 값은 정의에 의하여 0이 됩니다. 따라서, 위에 정의된 식은 $k-1$차 방정식이 되며, 이때 $b_i$는

 

\[ b_i = a_i - c_1 a_{i-1} - \cdots - c_i a_0 \]

 

가 됩니다. 이 $b_i$들의 값을 모두 구하는 것은 단순 for문을 이용하면 $\mathcal{O}(k^2)$이 소요됩니다. 이렇게 방정식을 구했다면 저희가 원하는 다음 결과를 얻을 수 있습니다.

 

\[ a_0 + a_1 x + a_2 x^2 + \cdots = \frac{b_0 + b_1 x + \cdots + b_{k-1} x^{k-1}}{1 - c_1 x - c_2 x^2 - \cdots - c_k x^k} \]

 

따라서, 5. 혹은 6.의 방법을 이용하면 초기 $T$개의 항 $a_0, a_1, \cdots , a_{T-1}$은 $ \mathcal{O}(T \log T) $, 특정한 $N$번째 항 $a_N$을 구하는 것은 $\mathcal{O}(k \log k \log N)$의 시간만에 계산을 할 수 있습니다.

 

8. 유리식들의 합 $\mathcal{O}(T \log^2 T)$

 

다항식 $f_1(x), f_2(x), \cdots, f_n(x)$와 다항식 $g_1(x), g_2(x), \cdots, g_n(x)$가 주어질 때, $\frac{f_1(x)}{g_1(x)} + \frac{f_2(x)}{g_2(x)} + \cdots + \frac{f_n(x)}{g_n(x)}$는 $\frac{f(x)}{g(x)}$꼴로 표현할 수 있습니다. 만약, $f,g$의 차수가 모두 $T$보다 작다고 가정하면, $\frac{f(x)}{g(x)}$는 $\mathcal{O}(T \log^2 T)$에 계산이 가능합니다.

 

$\frac{f_1(x)}{g_1(x)} + \frac{f_2(x)}{g_2(x)} + \cdots + \frac{f_{n/2}(x)}{g_{n/2}(x)}$를 $\frac{a(x)}{b(x)}$, $\frac{f_{n/2+1}(x)}{g_{n/2+1}(x)} +  \cdots + \frac{f_n(x)}{g_n(x)}$을 $\frac{c(x)}{d(x)}$로 정의하면, $\frac{a(x)}{b(x)} + \frac{c(x)}{d(x)}$는 $\mathcal{O}(T \log T)$에 계산이 가능합니다. 이런식으로 분할정복을 해나가면 $\mathcal{O}(T \log^2 T)$에 계산이 가능합니다. 이때, 유리식을 2등분할때 등분한 유리식의 차수가 불균형해서 문제가 될 수 있다고 생각할 수 있는데, parallel binary search 시간복잡도 분석할때와 비슷하다고 생각하면 $\mathcal{O}(T \log^2 T)$임을 쉽게 증명할 수 있습니다.

 

(미확실) 이 방법을 이용하면 다항식환 위에서의 Chinese Remainder Theorem을 빠르게 계산할 수 있을것 같은데... 긴가민가하군요.

 

9. $ \sum_{i=1}^n a_i^j$를 $T$미만의 모든 $j$에 대해서 계산 $\mathcal{O}(T \log^2 T)$

 

수열 $a_1, a_2, \cdots, a_n$이 주어졌을때, $b_k = a_1^k + a_2^k + \cdots + a_n^k$로 정의합시다. 이때, $b_0, b_1, \cdots, b_{T-1}$을 빠르게 계산하는 방법입니다. 다음 식에 주목을 해봅시다.

 

\[ \frac{1}{1-a_i x} = 1 + a_i x + a_i^2 x^2 + a_i^3 x^3 + \cdots \]

 

따라서, 다음이 성립합니다.

 

\[ \sum_{i=1}^n \frac{1}{1-a_i x} = b_0 + b_1 x + b_2 x + \cdots \]

 

$ \frac{1}{1-a_i x} $ mod $ x^T $를 하나하나 계산해서 더해주는건 시간이 오래걸리므로 다른 방법을 사용해야합니다. 8.에서 정의한 유리식의 합공식을 이용하여 $ \sum_{i=1}^n \frac{1}{1-a_i x} $를 계산해준 뒤, $ Z_p[x] \text{ mod } x^T  $ 위에서 다시 생각해주면 됩니다.

 

만약, $T$미만의 모든 $j$에 대해서 계산하는것이 아닌 모든 $j$에 대해서 계산해주고자 한다면, 6.에서 정의한 Bostan-Mori 방법을 사용하면 $\mathcal{O}(n \log n \log N)$에 계산이 가능합니다. 

 

10. $f(x) f(rx) f(r^2) \cdots f(r^{n-1} x) $의 계산 $\mathcal{O}(T \log T)$

 

$F(x) = f(x) f(rx) \cdots f(r^{n-1} x) $로 정의할때, $\log F(x) = \sum_{i=0}^{n-1} \log f(r^i x) $가 성립합니다. $\log f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{T-1} x^{T-1}$을 계산하였다고 가정합시다. 이 과정은 $\mathcal{O}(T \log T)$의 시간이 걸립니다. 그러면, $\log f(r^i x)$들의 합은 등비수열의 합공식을 사용하면 쉽게 계산할 수 있고, 다음과 같이 되는것을 알 수 있습니다.

 

\[ \sum_{i=0}^{n-1} \log f(r^i x) = n a_0 + \frac{r^n - 1}{r-1} a_1 x + \frac{r^{2n} - 1}{r^2 -1} a_2 x^2 + \cdots + \frac{r^{nT-n} -1}{r^{T-1} -1} a_{T-1} x^{T-1} \]

 

이 식을 다시 exp해주면 저희가 원하는 $F(x)$를 얻을 수 있습니다.

 

11. 초기 $T$개의 Bell 수 $\mathcal{O}(T \log T)$

 

$n$번째 Bell 수 $B_n$은 크기 $n$인 집합의 partition의 개수로 정의합니다. 제 2종 스털링수 $ \begin{Bmatrix} n \\ k \end{Bmatrix} $는 크기 $n$인 집합을 $k$개의 partition으로 나누는 개수를 의미하므로, 일반적으로 다음 식이 성립합니다.

 

\[ B_n = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} \]

 

Bell수의 지수적 생성함수(그냥 생성함수가 아닙니다!)를 생각하면, 다음 식이 성립하는것을 알 수 있습니다.

 

\[ \sum_{i=0}^\infty B_i \frac{ x^i }{i!} = e^{e^x -1} \]

 

따라서 $ Z_p[x] \text{ mod } x^T $ 위에서 exp연산을 2번 하면 초기 $T$개의 Bell 수를 계산할 수 있습니다.

 

12. 제 1종 스털링 수 $\mathcal{O}(n \log n)$

 

수열 $a_1, a_2, \cdots, a_n$을 $ \{ 1,2, \cdots, n \} $ 의 permutation이라고 정의합시다. 그러면, 수열 $a$는 여러개의 cycle들로 분할이 됩니다. 이처럼 수열이 $ \{ 1,2, \cdots, n \} $ 의 permutation이고, 분할되는 cycle의 개수가 $k$개가 되는 수열 $a_1,a_2, \cdots, a_n$의 개수를 제 1종 스털링 수 $ \begin{bmatrix} n \\ k \end{bmatrix} $ 라고 정의합니다. 제 1종 스털링 수는 다음과 같은 점화식 관계를 만족한다는 것이 알려져 있습니다.

 

\[ \begin{bmatrix} n \\ k \end{bmatrix} = \begin{bmatrix} n-1 \\ k-1 \end{bmatrix} + (n-1) \begin{bmatrix} n-1 \\ k \end{bmatrix} \]

 

제 1종 스털링 수는 다음식을 만족합니다.

 

\[ \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} x^k = x (x+1) (x+2) \cdots (x+n-1) \]

 

따라서, 오른쪽 다항식을 빠르게 계산할 수 있다면 주어진 n에 대하여 $ \begin{bmatrix} n \\ k \end{bmatrix} $ 형태의 모든 제 1종 스털링 수를 계산할 수 있습니다. 오른쪽 다항식은 빠른 거듭제곱 계산 비슷한 방법으로 빠르게 계산이 가능합니다.

 

$n$이 홀수라면 $x(x+1) \cdots (x+n-2)$를 계산한 다음 이 식에 $(x+n-1)$을 곱하면 됩니다. 만약 $n=2k$가 짝수라면, $f(x) = x(x+1) \cdots (x+k-1)$로 정의할때, $x(x+1) \cdots (x+2k-1) = f(x) f(x+k)$가 성립하게 됩니다. 이때, $f(x)$를 계산 한 뒤 $f(x+k)$는 1.에서 정의한 Polynomial Taylor Shift를 사용하면 $\mathcal{O}(n \log n)$에 계산이 가능하므로, $x(x+1) \cdots (x+2k-1)$를 빠르게 계산할 수 있습니다. 시간복잡도는 $\mathcal{O}(n \log^2 n)$이 될것 같지만, 실제로는 계산을 진행하며 차수가 계속 절반씩 떨어지기 때문에, $\mathcal{O}(n \log n)$이 됩니다.

 

13. 제 2종 스털링 수 $\mathcal{O}(n \log n)$

 

제 2종 스털링 수 $\begin{Bmatrix} n \\ k \end{Bmatrix} $는 크기 $n$인 집합이 있을때 그 집합을 $k$개의 공집합이 아닌 부분집합들로 나누는 방법의 수입니다. 제 2종 스털링 수는 다음과 같은 재귀적인 식으로 풀 수 있다는 것이 알려져 있습니다.

 

\[ \begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix} + k \begin{Bmatrix} n-1 \\ k \end{Bmatrix} \]

 

제 2종 스털링 수는 다음 식을 만족합니다.

 

\[ \begin{Bmatrix} n \\ k \end{Bmatrix} = \frac{1}{k!} \sum_{i=0}^k (-1)^{k-i} \begin{pmatrix} k \\ i \end{pmatrix} i^n \]

 

위 식과 FFT를 잘 이용하면 주어진 $n$에 대해 모든 제 2종 스털링 수 $\begin{Bmatrix} n \\ k \end{Bmatrix} $를 $\mathcal{O}(n \log n)$에 계산할 수 있습니다. 어떤 두 다항식을 만들어서 FFT를 해야하는지에 대한 설명은 생략하겠습니다(아마 쉽게 알 수 있을거라 생각합니다)

 

14. $ \sum_{i=0}^n A_i (x+a)^i (x+b)^{T-i} $의 계산 $ \mathcal{O}(T \log T) $

 

$f(x) = \sum_{i=0}^n A_i (x+a)^i (x+b)^{T-i}$로 정의합시다. 그러면, $f(x-b) = \sum_{i=0}^n A_i (x+a-b)^i x^{T-i} = x^T \sum_{i=0}^n A_i (\frac{x+a-b}{x})^i = x^T \sum_{i=0}^n (a-b)^i A_i (\frac{1}{x} + \frac{1}{a-b})^i $가 성립합니다. $g(t) = \sum_{i=0}^n (a-b)^i A_i (t + \frac{1}{a-b})^i$로 정의합시다. 그러면, $g(t-\frac{1}{a-b}) = \sum_{i=0}^n (a-b)^i A_i t^i$가 성립하여, $g(t-\frac{1}{a-b})$를 $\mathcal{O}(T)$에 계산할 수 있습니다. 이제, 1.에서 정의한 Polynomial Taylor Shift를 2번 사용하여 $f(x)$를 역추적해나가면 됩니다.

 

여담으로, 이러한 형태의 다항식을 계산해내라는 문제가 ARC-F번에 출제된적이 있던것 같습니다.

 

15. Multipoint Evaluation  $ \mathcal{O}(n \log^2 n) $

 

$T-1$차 다항식 $f$과 $a_1, a_2, \cdots, a_n$이 주어질때, $f(a_1), f(a_2), \cdots, f(a_n)$의 값을 빠르게 구해내는 알고리즘입니다. 하나하나 일일히 계산한다면 $\mathcal{O}(Tn)$의 시간이 소모되기 때문에, 더 빠른 방법이 필요합니다.

다음 사실이 성립합니다.

 

\[ f(a) = f(x) \text{ mod } (x-a) \]

 

따라서, 다음 함수를 정의하겠습니다.

 

\[ g(L,R) = f(x) \text{ mod } (x-a_L)(x-a_{L+1})\cdots(x-a_R) \]

 

이때, $g(L,R)$은 다음 분할정복을 이용해서 계산 가능합니다.

1) $g(1,n)$을 먼저 계산해둡니다. 두 다항식의 몫과 나머지를 계산하는 방법을 이용하면 $\mathcal{O}(n \log n + T \log T)$의 시간이 필요합니다. 이제, 일반적으로 $g(L,R)$의 값을 알고있다고 가정하겠습니다.

2) $h = \frac{L+R}{2}$로 정의합니다. 그러면, $g(L,h) = g(L,R) \text{ mod } (x-a_L) \cdots (x-a_h), g(h+1,R) = g(L,R) \text{ mod } (x-a_{h+1}) \cdots (x-a_R)$이 되어 $g(L,h), g(h+1,R)$의 값 역시 알 수 있습니다.

3) 2) 과정을 반복하여 $L=R$이 될때까지 반복합니다. 만약, $L=R$이 된다면 거기서 함수를 종료하며, 이때 $f(a_L) = g(L,L)$이 됩니다.

 

중간중간에 나오는 $(x-a_i)$들의 곱형태의 다항식들은 미리 전부 계산해두면 $\mathcal{O}(n \log^2 n)$의 시간만이 소요됩니다. 그리고 중간중간 계산하는 나머지를 계산하는 연산도 전부 합치면 $\mathcal{O}(n \log^2 n)$이 된다는 것을 알 수 있기 때문에, 전체 시간복잡도는 $\mathcal{O}(n \log^2 n)$가 됩니다.

 

16. Lagrange Interpolation $ \mathcal{O}(n \log^2 n) $

 

15.의 반대버전입니다. $a_1, a_2, \cdots, a_n$가 주어지고, 또한 $b_1, b_2, \cdots, b_n$이 주어질때, $f(a_i) = b_i$를 만족하는 $n-1$차 다항식 $f$를 찾는 문제입니다. 15.에서 썼던 아이디어를 그대로 사용하면, $f$는 다음 방정식의 해라는 것을 알 수 있습니다.

 

\[ \begin{align} &f(x) \equiv b_1 \text{ mod } (x-a_1) \\ &f(x) \equiv b_2 \text{ mod } (x-a_2) \\ &\cdots \\ &f(x) \equiv b_n \text{ mod } (x-a_n) \end{align} \]

 

따라서, $f(x)$는 다항식 위에서의 Chinese Remainder Theorem을 이용하면 계산할 수 있고, 중간 계산을 전부 건너뛰면 $f(x)$는 다음 식이 되는것을 알 수 있습니다.

 

\[ f(x) = \sum_{i=1}^n b_i \prod_{i \neq j} \frac{x-a_j}{a_i-a_j} \]

 

이 식의 값은 어떻게 계산할까요? $g(x) = (x-a_1)(x-a_2)\cdots(x-a_n)$으로 정의합니다. $g$는 분할정복 + FFT로 $\mathcal{O}(n \log^2 n)$의 시간에 계산할 수 있습니다. 이때, 계산을 해보면 다음이 성립하는것을 알 수 있습니다.

 

\[ g^\prime(a_i) = \prod_{i \neq j} (a_i - a_j) \]

 

즉, $f(x) = g(x) \sum_{i=1}^n \frac{b_i}{g^\prime(a_i) (x-a_i)}$가 성립함을 알 수 있습니다. 15.에서 정의한 Multipoint Evaluation으로 $g^\prime(a_1), g^\prime(a_2), \cdots, g^\prime(a_n)$을 빠르게 구하고, 8.에서 정의한 $n$개의 유리식의 합 고속화, 혹은 2.에서 정의한 전개 후 Harmonic Series를 이용한 시간복잡도 분석을 사용하면 $f(x)$를 계산할 수 있습니다.

 

17. Shift of Sampling Points of Polynomial

 

미완성된 토픽입니다.

 

$T$차 다항식 $f$가 주어지고, $f(0), f(1), \cdots, f(T)$의 값이 주어졌을때, 임의의 점 $a$에서의 값 $f(a)$를 계산하는 방법입니다. 이때 시간복잡도가 $a$에 depend하지 않는것이 핵심입니다, 즉 $a = 10^{18}$처럼 매우 큰 값이 들어와도 빠르게 계산할 수 있습니다. $f(a)$의 값이 $\mathcal{O}(N)$에 계산 할 수 있다는 것이 알려져있지만, 16.에서 정의한 Lagrange Interpolation으로 $f$를 직접 계산해서 $f(a)$를 구해도 상관 없습니다.(이 경우, 시간복잡도는 $\mathcal{O}(N \log^2 N)$ 입니다.)

 

18. $\sum_{n=0}^N n^k$ 를 $T$미만의 모든 $k$에 대해서 계산 $ \mathcal{O}(T \log T) $

 

$a_k = \sum_{n=0}^N n^k$로 정의합시다. 그러면, 다음이 성립합니다.

 

\[ 1 + e^x + e^{2x} + \cdots + e^{Nx} = \sum_{i=0}^\infty a_i \frac{x^i}{i!}  \]

 

이때, 좌변식은 등비수열식을 이용하면 $\frac{e^{(N+1)x} -1}{e^x - 1}$이 되고, $e^{(N+1)x}-1$은 $e^x-1$을 계산한뒤 $x$를 $(N+1)x$로 바꾸면 되므로, 총 $\mathcal{O}(T \log T)$의 시간에 $1 + e^x + e^{2x} + \cdots + e^{Nx}$ mod $x^T$를 계산할 수 있습니다. 이제 각 계수를 비교하면, $a_0, a_1, \cdots, a_{T-1}$을 계산할 수 있습니다.

 

19. 초기 $T$개의 베르누이 수 $ \mathcal{O}(T \log T) $

 

다음과 같은 식이 성립합니다.

 

$ \frac{x}{e^x-1} = \sum_{n=0}^\infty \frac{ B_n x^n}{n!} $

 

따라서 다항식의 exp와 inv를 잘 취해주는 것으로 초기 $T$개의 베르누이수를 쉽게 구해줄 수 있습니다.

 

20. $\sum_{n=0}^N n^k r^n , \sum_{n=0}^\infty n^k r^n $의 계산 $\mathcal{O}(k \log k \log N)$

 

확률, 기댓값과 관련된 문제에서 자주 보이는 식입니다. $k,N$이 주어질 때, $\sum_{n=0}^N n^k r^n , \sum_{n=0}^\infty n^k r^n $를 계산하는 방법입니다.

 

$0 \leq r < 1$이라고 가정합니다. 그것이 아니라면, 수식이 발산하기 때문에 구할 수 없습니다.

먼저, 다음 결과를 저희는 알고 있습니다.

 

$ \sum_{n=0}^\infty x^n = \frac{1}{1-x} = f_0(x)$

 

이 식들을 미분해나가면 다음과 같은 결과를 알 수 있습니다.

 

$ \sum_{n=0}^\infty n x^n = \frac{x}{(1-x)^2} $

$ \sum_{n=0}^\infty n^2 x^n = x (\frac{x}{(1-x)^2})^\prime $

...

$f(x)$를 $n^k$의 생성함수라고 가정합시다. 즉, $f(x) = 0^k + 1^k x^1 + 2^k x^2 + \cdots $라고 정의합시다. 위에서 말한 방법을 반복하다보면, 간단하게 $f(x) = \frac{g(x)}{(1-x)^{k+1}}$ 형태가 됨을 알 수 있습니다. $g(x)$를 계산하는 것은 간단합니다. $g(x)$의 차수가 $k$이하가 될것이므로, $f(x)$의 첫 $k+1$개의 항을 계산한 뒤, $(1-x)^{k+1} f(x)$ mod $x^{k+1}$을 계산해주면 $g(x)$를 구할 수 있습니다. 따라서, $g(x)$는 총 $\mathcal{O}(k \log k)$의 시간에 계산할 수 있습니다( $\mathcal{O}(k)$ 만에도 가능한것 같지만 이건 진짜로 생성함수의 규칙을 찾아내야만 하는것 같습니다. 너무 어려우니 생략).

 

위의 식을 이용하면 $n^k r^n$의 생성함수는 $f(rx)$라는 것을 알 수 있고, 더 응용하면 $ \sum_{n=0}^N n^k r^n $의 생성함수는 $\frac{f(rx)}{1-x}$가 되는것을 알 수 있습니다. 따라서, 최종적으로 다음이 성립합니다. ($c$는 적당한 상수, $g(x)$는 $k$차 이하의 적당한 다항식)

 

\[ \sum_{n=0}^N n^k r^n \text{의 생성함수} = \frac{ g(rx) }{(1-x)(1-rx)^{k+1}} = \frac{c}{1-x} + \frac{h(x)}{(1-rx)^{k+1}} \]

 

$c$는 어떻게 구할 수 있을까요? $\frac{ g(rx) }{(1-x)(1-rx)^{k+1}} = \frac{c}{1-x} + \frac{h(x)}{(1-rx)^{k+1}}$ 가 되기 때문에, $x=1$을 대입하면 $c=\frac{g(r)}{(1-r)^{k+1}}$ 라는것을 알 수 있습니다. $h$는 어떻게 구할 수 있을까요? $h(x) = \frac{g(rx) - c(1-rx)^{k+1}}{1-x}$가 되기 때문에 이 값을 계산하면 됩니다. 

 

이 $c,g$를 계산했다고 가정하면, 생성함수의 정의에 의하여 $ \sum_{n=0}^N n^k r^n = [x^N] \frac{c}{1-x} + [x^N] \frac{g(x)}{(1-rx)^{k+1}} $이 되고, 이 값은 6.에서 정의된 방법을 사용하면 됩니다.

 

만약 $N = \infty$면 어떻게 할까요? $ [x^N] \frac{h(x)}{(1-rx)^{k+1}} $은 $N$이 무한으로 갈때 $0$이 됩니다. 왜냐하면, $r$이 1보다 작고, 저 다항식의 $N$번째 계수는 $r^N$과 관련된 식으로 표현되기 때문입니다. 따라서,  $ \sum_{n=0}^\infty n^k r^n $ = $ [x^\infty] \frac{c}{1-x} = c$ 가 됩니다.

 

21. $\sum_{k=L}^{R} f(kx)$의 첫 $T$개의 항 계산 $\mathcal{O}(T \log T)$

 

$f(kx) = a_0 + a_1 x + a_2 x^2 + \cdots$ 라고 정의하겠습니다. 그러면,

 

\[ \sum_{k=0}^{T-1} f(kx) = T a_0 + \sum_k k a_1 x + \sum_k k^2 a_2 x^2 + \cdots \]

 

따라서, 18에서 정의된 방법을 사용하면 $ \sum_{k=0}^{T-1} f(kx) $를 $\mathcal{O}(T \log T)$ 시간에 계산할 수 있습니다. 그러므로, 원래 문제인 $\sum_{k=L}^{R} f(kx)$도 $\mathcal{O}(T \log T)$에 계산이 가능합니다.

 

22. $\prod_{k=L}^{R} f(kx)$의 계산

 

전체 식에 $ \log $를 씌우면 21.번 문제가 됩니다.

 

23. relaxed multiplication $\mathcal{O}(T \log^2 T)$

 

Online FFT, Relaxed Convolution등으로도 불리는 방법입니다. 다항식 $f$와 $g$가 주어질때, $h(x) = f(x) \times g(x)$를 계산하려고 하는데, $f$와 $g$의 계수가 한번에 주어지지 않는 경우의 문제입니다. 대표적으로, $[x^i]f(x)$를 계산하기 위하여 $[x^{i-1}]h(x)$의 계수가 필요한 경우, 다항식의 계수를 한꺼번에 구할 수 없게 됩니다.

 

다음과 같은 경우를 생각해봅시다. $i = 0,1,\cdots,T-1$순으로 다음 쿼리가 주어집니다.

 

$ [x^i]f(x)$와 $[x^i]g(x)$가 주어집니다. 이때, $[x^i]h(x)$를 계산하시오.

 

각 $i$마다 FFT를 하는 방법으로는 총 $\mathcal{O}(T^2 \log T)$의 시간이 걸리기에, 더 빠른 방법이 필요합니다.

 

다항식을 차수가 작은 순서부터 1,2,4,8...길이로 잘라봅시다. 즉, 다음과 같이 식을 적겠습니다.

$ f(x) = (a_0) + (a_1 x + a_2 x^2) + (a_3 x^3 + \cdots + a_6 x^6) + \cdots $

$ g(x) = (b_0) + (b_1 x + b_2 x^2) + (b_3 x^3 + \cdots + b_6 x^6) + \cdots $

저희가 만약 $f(x) \times g(x)$의 $n$차 계수를 보고 싶다면, $x^n$이 나올 수 있는 모든 다항식 쌍들을 보며 FFT를 진행해주면 됩니다. 예를 들어, $n=6$인 경우, 다음 다항식들의 곱만 계산하면 됩니다.

 

\[ \begin{align} &(a_0) \times (b_3 x^3 + \cdots + b_6 x^6) \\ &(a_1 x + a_2 x^2) \times (b_3 x^3 + \cdots + b_6 x^6) \\ &(a_3 x^3 + \cdots + a_6 x^6) \times (b_0) \\ &(a_3 x^3 + \cdots + a_6 x^6) \times (b_1 x + b_2 x^2) \\ &(a_3 x^3 + \cdots + a_6 x^6) \times (b_3 x^3 + \cdots + b_6 x^6) \end{align} \]

실제 이 다항식을 그대로 곱하면 다항식의 차수가 크기 때문에 시간 초과가 나올 수 있습니다. 그러므로 최저차수만큼을 미리 나누어줘서 차수를 줄여주는것이 유효합니다.(예를 들어, 최저차항이 $L$이고 최고차항이 $R$인 다항식을 고려할때, 미리 $x^L$로 나누어져서 $R-L$차 다항식으로 만들어 준 후 계산한뒤, 결과에 $x^L$을 곱하면 됩니다.) 또한, 어떠한 다항식 쌍을 곱했었다면, 그 뒤는 메모이제이션을 통하여 다시 곱하지 않도록 해줍시다.

 

시간 복잡도는 어떻게 될까요? 간단하게 $f$의 차수가 $2^K-2$라고 합시다. 그러면 $f$는 정확하게 길이 $1,2,\cdots, 2^{K-1}$인 다항식들로 쪼개지고, 이 다항식들의 계산에 소모되는 시간은 다음처럼 됩니다.

 

1) 먼저 모든 다항식 쌍에 대하여 곱셈을 해야합니다.  길이 $2^i$인 다항식과 $2^j$인 다항식을 곱하는것은 약 $2^{\max(i,j)} \log (2^K)$의 연산이 필요합니다.

2) 모든 다항식들의 쌍을 곱하였다면 그 후는 메모이제이션으로 곱셈을 불러오면 되기 때문에, $n$차 다항식의 곱의 원하는 차수를 불러오는것이 $\mathcal{O}(1)$이 걸린다고 볼 수 있습니다. 이때, 총 곱셈이 불러오는 횟수를 생각해보면, 길이 $2^i$인 다항식과 $2^j$인 다항식을 곱하는것이 약 $2^i+2^j$번 호출됩니다.

 

1)의 연산량은 $2^{K-1} K \times K + 2^{K-2} K \times (K-1) + 2^{K-3} K \times (K-2) + \cdots = \mathcal{O}(2^K K^2)$이 되며, 2)의 연산량은 $ 2 \times (2^0 + 2^1 + \cdots + 2^{K-1}) \times K = \mathcal{O}(2^K K) $ 가 됩니다. $T-1 = 2^K - 2$로 정의하면, $T-1$차 다항식 두개의 relaxed multiplication은 총 $\mathcal{O}(T \log^2 T)$에 계산을 할 수 있습니다.

 

 

24. $\prod_{i=1}^N (a_i x + b_i)^{c_i} $의 첫 $T$개의 항 $\mathcal{O}(N \log^2 N + T \log T)$

 

일반성을 잃지 않고 $b_i=1$이라고 가정하겠습니다. 만약, $b_i=0$이라면 $(a_i x)^{c_i}$을 따로 계산해서 마지막 결과에 곱해주면 되니 $b_i=0$인 케이스를 제외할 수 있고, $b_i \neq 0$라면 $(a_i x + b_i)^{c_i} = b_i^{c_i} (\frac{a_i}{b_i} x + 1)^{c_i}$가 되기 때문입니다.

 

$f(x) = \prod_{i=1}^N (a_i x + 1)^{c_i}$라고 정의하겠습니다. 그러면, 다음이 성립합니다.

 

\[ (\log f(x))^\prime = \sum_{i=1}^N \frac{a_i c_i}{a_i x + 1} \]

 

따라서, 8.에서 정의한 유리식의 합을 계산하면 $ \log f(x) $를 $\mathcal{O}(N \log^2 N)$ 시간에 계산 할 수 있습니다. $ \log $계산과 $e^f$ 계산은 $\mathcal{O}(T \log T)$의 시간이 걸리므로, 총 $\mathcal{O}(N \log^2 N + T \log T)$ 시간에 계산이 가능합니다.

25. $\sum_{i=1}^N a_i e^{b_i x}$ 의 첫 $T$개의 항 계산 $\mathcal{O}(N \log^2 N + T \log T)$

 

$e^{b_i x}$를 전개하면, 저희가 계산하려고 하는 다항식은 다음과 같이 되는것을 알 수 있습니다.

 

\[ \sum_{k=0}^{T-1} \frac{ \sum_{i=1}^N a_i b_i^k }{k!} x^k \]

 

하지만 이 식을 계산하는건 어렵기 때문에, 대신 이 식을 계산하겠습니다.

 

\[ \sum_{k=0}^{T-1} \sum_{i=1}^N a_i b_i^k x^k \] 

 

위 식을 계산 한뒤, $k$차 항의 계수를 각각 $k!$으로 나누면 원래 구하려고 하는 다항식이 되는것을 알 수 있습니다. 이때, 다음이 성립합니다.

 

\[ \begin{align} \sum_{k=0}^{T-1} \sum_{i=1}^N a_i b_i^k x^k &= \sum_{i=1}^N \sum_{k=0}^{T-1} a_i b_i^k x^k \\ &= \sum_{i=1}^N \frac{a_i}{1 - b_i x} \text{ mod } x^T \end{align} \]

 

따라서, $ \sum_{i=1}^N \frac{a_i}{1- b_i x}$를 계산하면 됩니다. 8.에서 정의한 유리식의 합 계산을 사용하면, 이 식은 $\mathcal{O}(N \log^2 N)$ 시간에 계산이 가능하며, 다항식 나누기를 하는데 $\mathcal{O}(T \log T)$ 시간이 걸리므로, 총 $\mathcal{O}(N \log^2 N + T \log T)$의 시간에 계산을 할 수 있습니다.

 

마치며

 

원문은 Codeforces 닉네임 maspy님이 적으신 다항식에 관련된 글 https://maspypy.com/%e5%a4%9a%e9%a0%85%e5%bc%8f%e3%83%bb%e5%bd%a2%e5%bc%8f%e7%9a%84%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0-%e9%ab%98%e9%80%9f%e3%81%ab%e8%a8%88%e7%ae%97%e3%81%a7%e3%81%8d%e3%82%8b%e3%82%82%e3%81%ae#toc39 이며, maspy님의 허가를 받아서 한국어로 번역하였습니다. 번역하면서 제가 이해못한부분들이 많아 누락된 토픽이나 설명이 부족한 부분이 매우 많습니다. 계속 공부해나가면서 부족한 부분은 보완해나갈 예정입니다만, 솔직히 자신 없네요.

 

내용이 매우매우 어렵습니다. 하나하나 공부한다기 보다 PS에서 조합론, 특히 이상한 합을 계산하라는 문제가 나올때 라이브러리를 본다는 느낌으로 이 글을 검색해 찾아오는 용으로 쓰면 좋을것 같습니다(사실 저 자신도 그렇게 하려고 내용을 정리해봤습니다).