어려운 다항식 연산들에 대하여

2022.10.08) 현재 내용 수정, 추가중에 있습니다.

2023.10.05) 두 다항식의 gcd에 대한 내용을 추가했습니다.

 

요즘 PS판이 고여가면서(?) 옛날에는 엄청 어려웠던 알고리즘들이 요즘은 기본지식이 되어가는 경우가 종종 있습니다. 가장 대표적인 어려운 알고리즘중 하나가 FFT로, 예전에는 정말 아는 사람들만 아는 어려운 지식이었지만 최근에는 PS 하는 고인물들 사이에서는 기본지식처럼 되버린 알고리즘입니다. FFT에 관한 구체적인 지식은 건너뛰고 결과만 간략하게 말하면, "두 다항식을 빠르게 곱하는 방법"입니다. 하지만, "두 다항식을 곱하기"는 "여러 다항식 연산들" 중에서는 가장 쉽고, 직관적인 연산중 하나입니다(FFT가 쉽다는게 아닙니다! FFT는 충분히 아주아주 어려운 알고리즘입니다). 실제 다항식을 다루게 될 경우, "두 다항식 곱하기"보다 훨씬 어려운 연산들은 매우 많습니다. PS에서는 다항식 관련 계산으로 FFT가 가장 악명이 높고 어렵다고 알려져있지만, 나중에 들어서는 FFT보다 더 어려운 알고리즘을 다루게 될 수도 있다는 것입니다. 이번 글에서 소개할 #p Subset Sum과 Polynomial Taylor Shift가 바로 그것으로, 겉보기에는 아주 간단하지만 실제로 다루려면 아주 악랄한, FFT정도는 선녀로 보일 정도로 아주 악랄한 다항식 연산들을 다루게됩니다.

 

한번 그 악랄한 다항식 연산들에 대해 알아봅시다. 이 글에서는 다음과 같은 연산들을 다룰것입니다.

 

1) 다항식 $f,g$가 주어질때 $f \times g$의 계산 $ \mathcal{O}(T \log T) $

2) 다항식 $f$가 주어질때 $f^k$의 계산 $ \mathcal{O}(T \log T \log k) $

3) 다항식 $f$가 주어질때 $1/f$의 계산 $ \mathcal{O}(T \log T) $

3.1) $f$가 sparse일때 $1/f$의 계산 $ \mathcal{O}(TK) $

4) 다항식 $f$가 주어질때 $\log(f)$의 계산 $ \mathcal{O}(T \log T) $

4.1) $f$가 sparse일때 $\log(f)$의 계산 $ \mathcal{O}(TK) $

5) 다항식 $f$가 주어질때 $ \sqrt{f} $의 계산 $ \mathcal{O}(T \log T) $

5.1) $f$가 sparse일때 $\sqrt{f}$의 계산 $ \mathcal{O}(TK) $

6) 다항식 $f$가 주어질때 $ e^f $의 계산 $ \mathcal{O}(T \log T) $

6.1. $f$가 sparse일때 $e^f$의 계산 $ \mathcal{O}(TK) $

7) 다항식 $f$가 주어질때 $f^k$의 계산 $ \mathcal{O}(T \log T ) $

7.1) $f$가 sparse일때 $f^k$의 계산 $ \mathcal{O}(TK) $

8) 다항식 $f,g$가 주어질때 $f(g(x))$의 계산 $ \mathcal{O}((T^2 \log T) $

9) 다항식 $f$가 주어질때 $f$의 역함수 $f^{-1}$계산 $ \mathcal{O}(T^2 \log T) $

10) 다항식 $f,g$가 주어질때 $f$를 $g$로 나눈 몫과 나머지 계산 $ \mathcal{O}(T \log T) $

11) 다항식 $f,g$가 주어질때 두 다항식의 최대공약수 $ \mathcal{O}(T \log^2 T) $

0. 사전지식들

 

PS 사전지식으로는 FFT정도만 알고 있으면 충분합니다. 하지만, 수학 사전지식은 매우 많이 필요합니다. 모든 내용을 상세히 소개할 수 없어 간략하게만 소개하니, 모르는 내용은 위키피디아등 다른 매체를 찾아보는것을 추천드립니다.

 

1) 체(Field): 수학에서 자주 언급되는 대수적 구조중 하나로, 어떤 집합에서 "덧셈, 곱셈, 뺄셈, 나눗셈"이 잘 정의될때, 그 집합을 체라고 부릅니다. 예를 들어, 정수 집합($\mathbb{Z}$)는 체가 아닙니다. 왜냐하면, 두 정수를 더하고, 빼고, 곱하면 정수가 맞지만, 두 정수를 나누었을때 그 결과가 정수가 아닐 수 있기 때문에 나눗셈이 잘 정의되지 않기 때문입니다. 반면에, 유리수, 실수, 복소수 집합 ($\mathbb{Q,R,C}$)는 체입니다. 임의의 두 유리수를 더하고, 빼고, 곱하고, 나눠도 유리수기 때문입니다.

 

하지만 PS에서 이러한 체 구조를 사용하기엔 무리가 있습니다. 컴퓨터는 실수를 완벽히 저장할 수도 없고, 저장할 수 있다고 해도 숫자의 범위가 무한인데 컴퓨터는 무한한 값을 저장할 수 없습니다.(예를 들어, 10^10^10^10을 컴퓨터한테 저장하라고 하면 할 수 있을까요?) 그렇기에 실제 PS에서는 위에서 언급된 체와는 조금 다른 체를 사용하는데 바로 그것이

 

2) 유한체(Finite Field): 유한체입니다. 유한체란 체는 체인데, 집합의 크기가 유한인 체입니다. 예를 들어 위에서 언급한 $\mathbb{Q,R,C}$는 유한체가 아닙니다. 집합의 크기가 무한이기 때문입니다. 하지만 다음 구조는 어떨까요?

 

$ 0 $ mod $ m $ , $ 1 $ mod $ m $ , $ 2 $ mod $ m $ , $\cdots$ , $ m-1 $ mod $ m $

 

안타깝지만 이 구조는 체가 아닙니다. 덧셈,뺄셈,곱셈은 잘 정의가 되지만 나눗셈이 잘 정의가 되지 않기 때문입니다. 하지만, 만약 $m$이 소수라면, 놀랍게도 나눗셈이 잘 정의가 되고, 따라서 이 구조는 크기가 $m$인 유한체가 됩니다. 그리고 그 나눗셈은 다음과 같이 정의가 됩니다.

 

$ a $ mod $ p = a^{p-2} $ mod $ p $

 

이것을 페르마의 소정리라고 부릅니다. 이 집합 $ \{ 0,1, \cdots , p-1\} $을 $\mathbb{Z}_p$ 혹은 $\mathbb{Z} / \mathbb{pZ}$등으로 표기합니다. PS에서 주로 $p = 998244353$을 사용하기 때문에, 이 글에서 숫자가 들어있는 체를 언급할때는 무조건 $\mathbb{Z}_{998244353}$이라고 생각해주면 되겠습니다.

 

3) 환(Ring): 위에서 언급한 체를 약화시킨 개념으로, 어떤 집합이 "곱셈, 뺄셈, 덧셈"이 잘 정의되는 집합을 환이라 부릅니다. 예를 들어, 위에서 말한 $\mathbb{Z}$라던가 $\{0,1, \cdots, m-1\}$ mod $m$ 등이 바로 환입니다. 여러 환들 중에서 가장 유명하고, 또 이 글에서 계속 얘기될 환이 바로 다항식 환(Polynomial Ring)입니다. "모든 다항식들을 모은 집합"을 생각해봅시다. 임의의 두 다항식을 더하거나, 빼거나, 곱해도 항상 다항식이기 때문에 이 집합은 환이 됩니다. 주의할 점으로, 차수가 무한인 방정식은 다항식이 아닙니다. 예를 들어,

 

$ \frac{1}{1-x} = 1+x+x^2+\cdots$

 

는 차수가 무한이기 때문에 다항식이 아닙니다.

하지만 이 다항식 환을 다루는데 문제가 있습니다. 위의 체에서 언급한것과 마찬가지로 컴퓨터는 무한한 값을 저장하지 못합니다. 만약 차수가 아주아주아주아주아주 큰 다항식이 주어지면 컴퓨터는 저장하지 못한다는 것입니다. 따라서, PS에서는 다음과 같은 다항식 환을 사용합니다.

 

$ \mathbb{Z}_p[x] $ mod $x^T$

 

이는 $ a_0 + a_1 x + a_2 x^2 + \cdots + a_{T-1} x^{T-1} , a_i \in \mathbb{Z}_p $인 다항식들의 집합이라 생각하면 됩니다(차수가 T-1 이하고, 모든 계수가 $\mathbb{Z}_p$에 속한 다항식의 집합). 위의 유한체에서 했던것처럼 $T$가 좋은 값이면 위 다항식 환이 체가 되지 않을까 생각할 수 있겠지만, 이 다항식 환은 $T$의 값과 무관하게 항상 체가 될 수 없습니다. 헷갈리지 마시기 바랍니다. 주의할 점으로, $ T < p $가 성립해야합니다. 만약 $ T \geq p $라면, 아래 연산들이 제대로 계산되지 않습니다.

 

또한, 이 글에서 다항식 $f$의 $k$번째 차수를 $[x^k]f(x)$로 표기합니다. 즉, $a_0 = [x^0]f(x), a_1 = [x^1]f(x), \cdots$ 입니다.

 

4) 테일러 급수(Taylor Series): 다항식이 아닌 함수를 다항식으로 표기하는 방법입니다. 만약 주어진 함수$f$가 적당히 좋은 성질을 가진 함수라면(조금 더 수학적으로 엄밀하게, 해석적이라면), 다음 식이 성립합니다.

 

$ f(x) = f(0) + \frac{f^{\prime}(0)}{1!} x + \frac{f^{\prime \prime}(0)}{2!} x^2 + \cdots $

 

저희들이 $ \mathbb{Z}_p[x] $ mod $x^T$에서 다항식을 생각한다는 것을 잊지 마시기 바랍니다. 차수가 $T$이상인 다항식 부분을 날릴것이기 때문에, 다음처럼 쓸 수 있습니다.

$ f(x) = f(0) + \frac{f^{\prime}(0)}{1!} x + \frac{f^{\prime \prime}(0)}{2!} x^2 + \cdots + \frac{f^{(T-1)}(0)}{(T-1)!} x^{T-1} $

 

즉, 저희는 Taylor Series를 이용하여 다항식 뿐만 아닌 임의의 함수를 전부 다항식처럼 생각할 것입니다. 이것은 생성함수(Generating Function)처럼 초월함수를 생각해야하는 문제를 PS로 풀 수 있는 문제로 끌어내리는데 도움을 줍니다.

 

5) Newton Method: 수치해석에서 함수의 해를 찾는 알고리즘입니다. $f(x) = 0$의 해를 찾고 싶을때 다음과 같은 과정을 반복합니다.

 

$ x_{n+1} = x_n - \frac{f(x_n)}{f^{\prime}(x_n)} $

 

이 방법의 오차는 약 $\mathcal{O}(h^2)$이라는 것이 알려져 있습니다. 갑자기 PS에서 뜬금없이 수치해석 얘기를 왜 하는지 싶으실텐데, Newton Method의 진가는 입력이 굳이 숫자가 아니여도 된다는 점입니다. 이 Newton Method를 조금 개량하면 다음과 같은 "미친 생각"을 할 수 있습니다.

 

함수 $F$를 함수를 입력 받아서 함수를 내뱉는 함수라고 정의하고, 함수 $F$의 해가 $f$라고 정의합시다. 그렇다면, Newton Method에 의하면 

 

$ g_{n+1} = g_n - \frac{F(g_n)}{F^{\prime}(g_n)} $

 

라는 과정을 반복하면, 결국 다항식 $g_n$은 $f$로 수렴한다는 것을 보일 수 있습니다. 또한, Newton Method의 오차분석법을 그대로 이용하면 위 방법을 거치면 거칠때 오차가 일어나는 차수가 2배가 된다는 것을 보일 수 있습니다. 즉, 만약 $ f - g_n$이 $k$차 방정식이라면, $f - g_{n+1}$은 $2k$차 방정식이 되고, $f - g_{n+2}$는 $4k$차 방정식이 됩니다! 우리는 방정식을 $ \mathbb{Z}_p[x] $ mod $x^T$위에서 생각하기 때문에, 결국 $ \log T $번의 Newton Method를 거치면 $g_n$이 정확히 $f$와 같아진다는 것을 알 수 있습니다. 이 방법을 이용하여 온갖 괴랄한 함수 $f$를 $g_n$을 이용하여 계산할것입니다.

 

1. 다항식 $f,g$가 주어질때 $f \times g$의 계산 $ \mathcal{O}(T \log T) $

 

FFT를 이용하면 됩니다. 설명은 생략합니다.

 

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

2. 다항식 $f$가 주어질때 $f^k$의 계산 $ \mathcal{O}(T \log T \log k) $

 

만약 $k = 2t+1$ 이라면, $f^{2t+1}(x) = f^{2k}(x) \times f(x) $를 계산합니다.

만약 $k = 2t$ 라면, $f^{2t}(x) = f^{k}(x) \times f^{k}(x) $를 계산합니다.

이러면 곱하기가 약 $ 2 \log k $번이 필요하기 때문에, 시간복잡도는 약 $ \mathcal{O}(T \log T \log k) $이 됩니다.

하지만 이것보다 빠른 방법을 밑에서 다룰것입니다.

 

3. 다항식 $f$가 주어질때 $1/f$의 계산 $ \mathcal{O}(T \log T) $

 

Newton Method를 사용합니다. $F(h) = 1/h(x) - f(x)$로 정의합니다. 이 $F$의 해는 정확하게 $1/f(x)$가 됩니다. 또한, $F$를 미분하면 $-1/h^2(x)$가 됩니다. 따라서,

 

\[ \begin{align} g_{n+1}(x) &= g_n(x) - \frac{F(g_n(x))}{F^\prime(g_n(x))} \\ &= g_n(x) - \frac{\frac{1}{g_n(x)} - f(x)}{-\frac{1}{g_n^2(x)}}  \\ &= g_n(x)(2 - g_n(x)f(x))  \end{align} \]

 

가 성립합니다. 하지만, 사전지식에서 설명했듯 $g_n(x)$는 특정 차수가 넘어가면 오차가 생기기 때문에, 모든 항을 전부 저장할 필요는 없습니다. 저희는 $g_n(x)$를 $2^n-1$차 방정식으로 두고 싶습니다. 이를 위해서 위의 Newton Method를 적용 한뒤, 차수를 $2^n-1$이 되도록 깎아줍니다.

 

$ g_{n+1}(x) = g_n(x)(2 - g_n(x) (f(x) \text{ mod } x^{2^{n+1}} )) $ mod $ x^{2^{n+1}} $

 

 $g_0(x)$는 어떻게 해야할까요? 이 값은 간단하게 상수값으로 잡으면 되지만, Newton Method가 수렴하기 위해서는 이 상수값은 $[x^0]1/f(x)$와 같아야 합니다. $[x^0]1/f(x) = 1/[x^0]f(x)$가 되기 때문에, $g_0(x) = 1/[x^0]f(x)$로 잡으면 충분합니다.

 

시간복잡도는 어떻게 될까요? $ g_n(x), f(x) \text{ mod } x^{2^{n+1}} $가 $2^{n+1}-1$차 방정식이란걸 상기해주세요. 한번의 Newton Method에서 2번의 FFT가 필요하며, 각 FFT의 연산수를 합치면 $ \mathcal{O}( 2^n \log 2^n) $이 됩니다. 이 Newton Method를 총 $ \log T$번 하게 되므로, 총 연산수는

 

$ 2^0 \log 2^0 + 2^1 \log 2^1 + \cdots + 2^{\log T} \log 2^{\log T} $

 

가 됩니다. 이는 $ \mathcal{O}(T \log T) $ 입니다.

 

주의할 점으로, $1/f$를 계산하기 위해서는 $[x^0]f(x)$가 0이 아니여야합니다. 0이라면 애초에 $1/f$가 수학적으로 정의가 되지 않고, 실제 코드에서도 $g_0(x)$를 정의할때 0으로 나누기가 발생하기 때문에 오류를 내뱉게 됩니다.

 

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

3.1. $f$가 sparse일때 $1/f$의 계산 $ \mathcal{O}(TK) $

만약, $T-1$차 다항식 $f$가 $K$개의 계수를 뺀 나머지 계수가 0이라고 가정합시다(즉, $f$는 최대 $K$개의 단항식(monomial)의 합이라고 가정합시다). 그렇다면, 오히려 단순무식한 계산방법이 더 효과적일 수 있습니다.

 

$f(x) = a_{i_1} x^{i_1} + \cdots + a_{i_K} x^{i_K}, \frac{1}{f}(x) = c_0 + c_1 x + \cdots + c_{T-1} x^{T-1} $ 이라고 가정합시다. Inverse가 존재하기 위한 조건에 의하여 $i_1 = 0, a_{i_1} \neq 0$여야합니다. 그리고 만약 이것을 만족한다면, $c_i$는 귀납적인 방법으로 찾을 수 있습니다.

 

• 일반성을 잃지 않고 $i<0$이라면 $c_i = 0$이라고 정의합니다.
• $c_0 \times a_{i_1} = 1$이므로, $c_0 = \frac{1}{a_{i_1}}$입니다.
• 만약 $c_0, c_1, \cdots, c_{s-1}$을 계산했다고 가정합시다. 그렇다면, $ c_s \times a_{i_1} + c_{s-a_{i_2}} \times a_{i_2} + \cdots + c_{s-a_{i_K}} \times a_{i_K} = 0 $이 성립하므로, $ c_s = -\frac{ c_{s-a_{i_2}} \times a_{i_2} + \cdots + c_{s-a_{i_K}} \times a_{i_K} }{a_{i_1}} $ 가 됩니다.

각 $c_i$를 계산하는데 $\mathcal{O}(K)$의 연산이 필요하고, 이것을 $T$번 반복하므로, 시간복잡도는 $\mathcal{O}(TK)$ 입니다.

 

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

 

4. 다항식 $f$가 주어질때 $\log(f)$의 계산 $ \mathcal{O}(T \log T) $

 

일반적으로 다음 식이 성립합니다.

 

$ \log f(x) = \int \frac{f^\prime(x)}{f(x)} dx $

 

따라서 $ f^\prime(x) $를 계산하고, 3. 에서 배운 $1/f(x)$를 계산하는 법을 이용하여 $ \frac{f^\prime(x)}{f(x)} $를 계산한 뒤, 적분하면 됩니다. 미분, 적분하는 법은 그냥 다항식 미분,적분하는 방법을 그대로 사용하면 됩니다. 미분, 적분에 $ \mathcal{O}(T) $, $1/f(x)$를 계산하는데 $ \mathcal{O}(T \log T) $가 걸리므로 총 시간은 $ \mathcal{O}(T \log T) $가 됩니다.

 

3.과 마찬가지로 $[x^0]f(x)$가 0이라면 $\log f(x)$가 정의조차 되지 않고, 프로그램은 오류를 내뱉게 됩니다.

 

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

4.1. $f$가 sparse일때 $\log(f)$의 계산 $ \mathcal{O}(TK) $

 

3.1.에서 $f$가 sparse할때 $1/f$를 계산하는 것이 $ \mathcal{O}(TK) $라고 하였습니다. 미분과 적분은 각각 시간이 $\mathcal{O}(T)$의 시간이 걸리므로, $f$가 sparse할때 $ \log(f) $의 계산은 $ \mathcal{O}(TK) $ 시간만에 가능합니다.

 

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

 

5. 다항식 $f$가 주어질때 $ \sqrt{f} $의 계산 $ \mathcal{O}(T \log T) $

 

Newton Method를 이용합니다. $F(h) = h(x)^2 - f(x)$로 정의합니다. 이 $F$의 해는 정확하게 $\sqrt{f(x)}$가 됩니다. 또한, $F$를 미분하면 $2h(x)$가 됩니다. 따라서,

 

\[ \begin{align} g_{n+1}(x) &= g_n(x) - \frac{F(g_n(x))}{F^\prime(g_n(x))} \\ &= g_n(x) - \frac{g_n(x)^2 - f(x)}{2g_n(x)}  \\ &= \frac{g_n(x) + \frac{f(x)}{g_n(x)}}{2} \end{align} \]

가 성립합니다. 3.에서 말했던것처럼 $g_n(x)$의 차수를 제한하면, 최종 결과는 다음과 같습니다.

 

$ g_{n+1}(x) = \frac{g_n(x) + \frac{f(x) \text{ mod } x^{2^{n+1}} }{g_n(x)}}{2} \text{ mod } x^{2^{n+1}} $

 

$ g_0(x) $는 마찬가지로 상수면 충분하며, $ [x^0] \sqrt{f(x)} = \sqrt{ [x^0]f(x)} $와 같아야 합니다. 하지만 이 값은 어떻게 계산할까요? 즉, 다음을 계산할 수 있어야합니다.

 

$c$가 주어질때, $ d^2 = c $ mod $ p $ 가 되게 하는 $ d $ 찾기

 

이는 baby step giant step이라는 다른 알고리즘을 이용하면 계산할 수 있습니다. 이 블로그에서 굳이 설명은 하지 않겠습니다. 아무튼 $ \sqrt{ [x^0]f(x)} $ 는 $ \mathcal{O}(\sqrt{p} \log p) $ 시간만에 계산할 수 있습니다.

 

또한, 이 방법은 $ [x^0]f(x) $가 0인경우 제대로 동작하지 않는다는 문제가 있을 수 있습니다. 이 경우는 $ \sqrt{x^2f(x)} = x \sqrt{f(x)} $ 를 이용하여 $[x^0]f(x) \neq 0$이 되도록 만들어주면 됩니다. 만약 $f(x) = x, x^3$처럼 최저차항의 차수가 홀수여서 더 못당기는 경우 문제가 될 수 있습니다만, 이경우는 애초에 $ \sqrt{f(x)} $가 존재하지 않습니다.

 

시간복잡도 분석은 3.과 동일합니다. 

 

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

 

5.1. $f$가 sparse일때 $\sqrt{f}$의 계산 $ \mathcal{O}(TK) $

 

$\sqrt{f}$ = $f^{1/2}$가 성립하기 때문에 7.1.의 방법으로 푸는것이 가능합니다.

 

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

 

6. 다항식 $f$가 주어질때 $ e^f $의 계산 $ \mathcal{O}(T \log T) $

 

Newton Method를 이용합니다. $F(h) = \log h(x) - f(x)$로 정의합니다. 이 $F$의 해는 정확하게 $e^{f(x)}$가 됩니다. 또한, $F$를 미분하면 $1/h(x)$가 됩니다. 따라서,

 

\[ \begin{align} g_{n+1}(x) &= g_n(x) - \frac{F(g_n(x))}{F^\prime(g_n(x))} \\ &= g_n(x) - \frac{\log(g_n(x)) - f(x)}{\frac{1}{g_n(x)}}  \\ &= g_n(x) ( f(x) + 1 - \log(g_n(x)) ) \end{align} \]

 

$g_n(x)$의 차수를 제한하면,

 

$ g_{n+1}(x) = g_n(x) ( f(x) \text{ mod } x^{2^{n+1}} + 1 - \log(g_n(x)) ) \text{ mod } x^{2^{n+1}} $

 

가 됩니다. $g_0(x) = [x^0] e^{f(x)} = 1$이면 충분합니다.

 

주의할점으로, $ [x^0]f(x) = 0 $으로 가정합니다. 만약 $ [x^0]f(x) \neq 0 $이라면, $ e^f $의 계수들을 $Z_p$안에서 표현을 못하기 때문에 $ e^f $를 계산할 수 없습니다.

 

시간복잡도 분석은 3.과 동일합니다. 

 

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

6.1. $f$가 sparse일때 $e^f$의 계산 $ \mathcal{O}(TK) $

$f(x) = a_{i_1} x^{i_1} + \cdots + a_{i_K} x^{i_K}, F(x) = e^f(x) = c_0 + c_1 x + \cdots + c_{T-1} x^{T-1} $ 이라고 가정합시다. 이때, $[x^0]f(x) = 0$이여야 하기 때문에, $i_1>0$으로 가정합니다. 합성함수의 미분법에 의하여, 다음이 성립합니다.

 

$ F^\prime(x) = F(x) f^\prime(x)$

 

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

 

$ c_1 + 2 c_2 x + \cdots + (T-1) x_{T-1} x^{T-2} =  (c_0 + c_1 x + \cdots + (T-1) x^{T-1})( i_1 a_{i_1} x^{i_1 - 1} + \cdots + i_K a_{i_K} x^{i_K -1}) $

 

그러므로, $ F = e^f$의 계산은 다음과 같은 과정으로 구할 수 있습니다.

 

• 일반성을 잃지 않고 $i<0$이라면 $c_i = 0$이라고 정의합니다.
• $c_0 =1 $입니다.
• 만약 $c_0, c_1, \cdots, c_{s-1}$을 계산했다고 가정합시다. 그렇다면, $ s c_s = i_1 a_{i_1} \times c_{s- i_1} + i_2 a_{i_2} \times c_{s-i_2} + \cdots + i_K a_{i_K} \times c_{s- i_K} $가 성립하고, 모든 {i_j}는 0보다 크므로, $ c_s = \frac{ i_1 a_{i_1} \times c_{s-i_1} + \cdots + i_K a_{i_K} \times c_{s-i_K}}{s} $ 가 성립합니다.

각 $c_i$를 계산하는데 $\mathcal{O}(K)$의 연산이 필요하고, 이것을 $T$번 반복하므로, 시간복잡도는 $\mathcal{O}(TK)$ 입니다.

 

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

 

7. 다항식 $f$가 주어질때 $f^k$의 계산 $ \mathcal{O}(T \log T ) $

 

$f(x)^k = e^{k \log(f(x))}$가 되기 때문에, $f(x)$의 log를 계산하고, $k$배를 한뒤, 다시 exp를 취해주는 방법으로 $ \mathcal{O}(T \log T ) $에 계산이 가능합니다.

 

주의할 점으로, 이 방법은 $\log(f(x))$를 계산 못하는 경우가 있으니 그 경우가 되지 않도록 사전에 $f(x)$를 조작하고 사용해야합니다. 또한, 이 방법은 $k$가 정수가 아니고 유리수일때도 사용할 수 있는데, 만약 $k$가 유리수라면 $[x^0]f(x) \neq 0$여야 이 방법이 가능합니다. 계산중 $\log{f}$를 계산해야 하기 때문에, $[x^0]f(x) = 1$로 두도록 조작 후 사용할 것을 강력하게 추천드립니다.

 

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

 

7.1. $f$가 sparse일때 $f^k$의 계산 $ \mathcal{O}(TK) $

이 글에서 $k$와 $K$는 다릅니다. 혼동하지 마시기 바랍니다.

 

$f$가 sparse일때 $e^f, \log{(f)}$의 계산이 $ \mathcal{O}(TK) $므로, $f^k$역시 $ \mathcal{O}(TK) $에 계산이 가능합니다.

 

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

 

8. 다항식 $f,g$가 주어질때 $f(g(x))$의 계산 $ \mathcal{O}(T^2 \log T) $

 

$f(x)$의 차수를 절반으로 나눠가며 분할정복을 해가면 됩니다. $f(x) = s(x) + t(x) x^{\frac{ |f(x)| }{2}}$가 되도록 $s,t$를 정의합니다($s,t$의 차수는 $f$의 차수의 절반이하). 그러면,

 

$ f(g(x)) = s(g(x)) + t(g(x)) \times g(x)^{\frac{ |f(x)| }{2}} $

 

가 성립합니다. $f(x)$가 $n$차 다항식일때 $f(g(x))$를 계산하는데 드는 연산수를 $A(n)$으로 정의를 하면, 7.에서 정의한 빠른 거듭제곱 방법을 이용한 경우

 

$ A(n) = 2 A(\frac{n}{2}) + \mathcal{O}(T \log T) $

 

가 되게 됩니다. 이것을 계산하면 시간복잡도는 약 $ \mathcal{O}(T^2 \log T) $가 되는것을 알 수 있습니다. $ \mathcal{O}(T^2) $ 혹은 $ \mathcal{O}(T \log T)^{3/2}) $에도 계산이 가능한것 같습니다만, 이부분에 대해서는 제가 잘 알지 못합니다.

 

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

 

9. 다항식 $f$가 주어질때 $f$의 역함수 $f^{-1}$계산 $ \mathcal{O}(T^2 \log T) $

 

$f$가 $ [x^0]f(x) = 0, [x^1]f(x) \neq 0$을 만족하는 다항식이라고 가정합시다. 이때, $ f^{-1}(f(x)) = f(f^{-1}(x)) = x $를 만족하는 $f^{-1}$를 $f$의 역함수라고 부릅니다. $f^{-1}$의 계산을 위해서는 Newton Method를 이용합니다. $F(h) = f(h(x)) - x$로 정의합니다. 이 $F$의 해는 정확하게 $f^{-1}(x)$가 됩니다. 또한, $F$를 미분하면 $f^\prime(h(x))$가 됩니다. 따라서,

\[ \begin{align} g_{n+1}(x) &= g_n(x) - \frac{F(g_n(x))}{F^\prime(g_n(x))} \\ &= g_n(x) - \frac{ f(g_n(x)) - x }{f^\prime(g_n(x))} \end{align} \]

 

$ g_n(x) $의 차수를 제한하면,

 

$ g_{n+1}(x) = g_n(x) - \frac{ f(g_n(x)) - x \text{ mod } x^{2^{n+1}} }{f^\prime(g_n(x)) \text{ mod } x^{2^{n+1}} }  \text{ mod } x^{2^{n+1}} $

 

가 성립합니다. $f(g(x))$와 $f^\prime(g(x))$의 계산이 각각 $ \mathcal{O}(2^{2n} \log 2^n) $므로, 이 방법의 전체 시간복잡도 역시 $ \mathcal{O}(T^2 \log T) $ 가 됩니다. 만약 8.을 계산하는데 더 빠른 방법을 사용한다면, 이 과정의 시간복잡도 역시 줄어들게 됩니다.

 

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

 

10. 다항식 $f,g$가 주어질때 $f$를 $g$로 나눈 몫과 나머지 계산 $ \mathcal{O}(T \log T) $

 

먼저 $f$의 차수가 $g$의 차수 이상이라고 가정합니다. 만약 $f$의 차수가 $g$의 차수보다 작다면, 단순히 몫은 0, 나머지는 $f$가 됩니다.

 

$f(x) = h(x)g(x) + r(x)$라고 가정해봅시다($r$의 차수 < $g$의 차수). 양쪽식에 $x$대신 $x^{-1}$을 대입하면,

 

$f(x^{-1}) = h(x^{-1})g(x^{-1}) + r(x^{-1})$

 

이 됩니다. 이 식은 다항식이 아니기 때문에, 다항식처럼 만들어주기 위해 각 변에 $ x^{\deg(f)} $를 곱해주면,

 

$f(x^{-1}) x^{\deg(f)} = h(x^{-1}) x^{\deg(f) - \deg(g)} g(x^{-1}) x^{\deg(g)} + r(x^{-1}) x^{\deg(f)}  $

 

가 됩니다. 이때 중요한 것은 $ r(x^{-1}) x^{\deg{f}} $의 차수인데요, $r$의 차수가 $g$의 차수 미만이기 때문에, $ r(x^{-1}) x^{\deg{f}} $의 최저차항의 차수는 $ \deg(f) - \deg(g) + 1$ 이상입니다. 따라서, 다음이 성립합니다.

 

$ f(x^{-1}) x^{\deg(f)} = h(x^{-1}) x^{\deg(f) - \deg(g)} g(x^{-1}) x^{\deg(g)} \text{ mod } x^{\deg(f) - \deg(g) +1} $

 

즉, $ h(x^{-1}) x^{\deg(f) - \deg(g)} = \frac{f(x^{-1}) x^{\deg(f)}}{g(x^{-1}) x^{\deg(g)}} \text{ mod } x^{\deg(f) - \deg(g) +1} $가 되게 됩니다. 그런데, $h$의 차수가 정확하게 $\deg(f) - \deg(g)$이기 때문에, $ h(x^{-1}) x^{\deg(f) - \deg(g)} $는 그냥 

$ \frac{f(x^{-1}) x^{\deg(f)}}{g(x^{-1}) x^{\deg(g)}} $가 되게 됩니다.

 

이 문단에서 계속 보이는 $f(x^{-1}) x^{\deg(f)}$는 무엇일까요? 어려운건 아니고 그냥 계수를 뒤집은 다항식이 됩니다. 즉, 만약 $f(x) = c_0 + c_1 x + \cdots + c_{T-1} x^{T-1}$이라면, $f(x^{-1}) x^{\deg(f)} = c_{T-1} + c_{T-2} x + \cdots + c_0 x^{T-1} $ 입니다. 이 사실을 이용하면 $f,g$를 뒤집고, 뒤집은 두 다항식을 나누고, 나눈 결과를 다시 뒤집으면 그 결과가 몫인 $h$가 됩니다. 나머지 $r$은 $f - gh$를 직접 계산하면 구할 수 있습니다.

 

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

 

11. 다항식 $f,g$가 주어질때 두 다항식의 최대공약수 $ \mathcal{O}(T \log^2 T) $

https://hyperbolic.tistory.com/10 에 적었습니다.

 

마치며

https://judge.yosupo.jp/

Library Checker

 

여기서 Math, Polynomial 탭에 들어가면 위에 설명한 방법들을 검증할 수 있는 문제들이 나옵니다. 익명으로도 낼 수 있으니 참고 바랍니다.

 

치명적인 내용 오류가 있지 않는이상 내용을 고치거나 추가할 예정은 없습니다. 질문은 환영입니다.