다항식과 급수에 대한 연산¶
경쟁 프로그래밍의 문제, 특히 어떤 종류의 열거를 포함하는 문제는 다항식과 형식적 멱급수에 대한 계산으로 문제를 환원하여 해결하는 경우가 많습니다.
여기에는 다항식 곱셈, 보간과 같은 개념과 다항식 로그 및 지수와 같은 더 복잡한 개념이 포함됩니다. 이 글에서는 이러한 연산과 그에 대한 일반적인 접근 방식을 간략히 개관합니다.
기본 개념과 사실¶
이 절에서는 다양한 다항식 연산의 정의와 "직관적인" 성질에 더 초점을 맞춥니다. 이들의 구현과 복잡도에 관한 기술적 세부 사항은 이후 절에서 다룹니다.
다항식 곱셈¶
정의
일변수 다항식은 $A(x) = a_0 + a_1 x + \dots + a_n x^n$ 꼴의 식입니다.
값 $a_0, \dots, a_n$은 다항식의 계수이며, 일반적으로 어떤 수의 집합이나 수와 유사한 구조에서 취합니다. 이 글에서는 계수를 어떤 체에서 취한다고 가정하는데, 이는 덧셈, 뺄셈, 곱셈, 나눗셈 연산이 ($0$으로 나누는 경우를 제외하고) 잘 정의되며 대체로 실수와 비슷하게 동작한다는 뜻입니다.
이러한 체의 대표적인 예는 소수 $p$를 법으로 하는 나머지들의 체입니다.
이 글에서 다루는 다항식은 이 종류뿐이므로, 간단히 하기 위해 일변수라는 용어는 생략하겠습니다. 또한 문맥상 이해할 수 있는 경우에는 가능한 한 $A(x)$ 대신 $A$라고 쓰겠습니다. $a_n \neq 0$이거나 $A(x)=0$이라고 가정합니다.
정의
두 다항식의 곱은 이를 산술식으로 전개하여 정의합니다:
$C(x)$의 계수들의 수열 $c_0, c_1, \dots, c_{n+m}$을 $a_0, \dots, a_n$과 $b_0, \dots, b_m$의 합성곱이라고 합니다.
정의
$a_n \neq 0$인 다항식 $A$의 차수는 $\deg A = n$으로 정의합니다.
일관성을 위해 $A(x) = 0$의 차수는 $\deg A = -\infty$로 정의합니다.
이 정의에서는 임의의 다항식 $A$와 $B$에 대해 $\deg AB = \deg A + \deg B$가 성립합니다.
합성곱은 많은 열거 문제를 해결하는 기반입니다.
Example
첫 번째 종류의 물건이 $n$개, 두 번째 종류의 물건이 $m$개 있습니다.
첫 번째 종류의 물건들의 가치는 $a_1, \dots, a_n$이고, 두 번째 종류의 물건들의 가치는 $b_1, \dots, b_m$입니다.
첫 번째 종류의 물건 하나와 두 번째 종류의 물건 하나를 고릅니다. 총 가치 $k$를 얻는 방법은 몇 가지입니까?
풀이
곱 $(x^{a_1} + \dots + x^{a_n})(x^{b_1} + \dots + x^{b_m})$을 생각해 봅시다. 이를 전개하면 각 단항식은 쌍 $(a_i, b_j)$에 대응하며 $x^{a_i+b_j}$의 계수에 기여합니다. 다시 말해, 답은 이 곱에서 $x^k$의 계수입니다.
Example
$6$면체 주사위를 $n$번 던지고 모든 던지기의 결과를 더합니다. 합이 $k$가 될 확률은 얼마입니까?
풀이
답은 합이 $k$인 결과의 수를 전체 결과의 수인 $6^n$으로 나눈 값입니다.
합이 $k$인 결과의 수는 얼마입니까? $n=1$인 경우, 이는 다항식 $A(x) = x^1+x^2+\dots+x^6$으로 나타낼 수 있습니다.
$n=2$인 경우, 위 예시와 같은 방법을 사용하면 이는 다항식 $(x^1+x^2+\dots+x^6)^2$으로 나타난다는 결론을 얻습니다.
따라서 문제의 답은 $(x^1+x^2+\dots+x^6)^n$의 $k$번째 계수를 $6^n$으로 나눈 값입니다.
다항식 $A(x)$에서 $x^k$의 계수는 간단히 $[x^k]A$로 표기합니다.
형식적 멱급수¶
정의
형식적 멱급수는 수렴 여부와 관계없이 다루는 무한합 $A(x) = a_0 + a_1 x + a_2 x^2 + \dots$입니다.
다시 말해, 예를 들어 합 $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots=2$를 생각할 때, 우리는 항의 개수가 무한대로 갈 때 이 합이 $2$로 수렴한다는 뜻으로 받아들입니다. 그러나 형식적 급수는 오직 그것을 이루는 수열의 관점에서만 다룹니다.
정의
형식적 멱급수 $A(x)$와 $B(x)$의 곱 역시 이를 산술식처럼 전개하여 정의합니다:
여기서 계수 $c_0, c_1, \dots$는 다음과 같은 유한합으로 정의됩니다
수열 $c_0, c_1, \dots$는 $a_0, a_1, \dots$와 $b_0, b_1, \dots$의 합성곱이라고도 불리며, 이는 이 개념을 무한 수열로 일반화한 것입니다.
따라서 다항식은 계수의 개수가 유한한 형식적 멱급수로 볼 수 있습니다.
형식적 멱급수는 열거 조합론에서 중요한 역할을 하며, 그곳에서는 다양한 수열의 생성함수로서 연구됩니다. 안타깝게도 생성함수와 그 배경에 있는 직관에 대한 자세한 설명은 이 글의 범위를 벗어나므로, 조합론적 의미에 대해 더 알고 싶은 독자는 예를 들어 이곳을 참고하십시오.
다만 아주 간단히 언급하자면, $A(x)$와 $B(x)$가 어떤 대상들을 그 안에 있는 "원자"의 개수로 세는 수열(예: 트리를 정점의 개수로 세는 경우)의 생성함수라면, 곱 $A(x) B(x)$는 종류 $A$와 $B$의 대상으로 이루어진 쌍으로 묘사할 수 있는 대상들을 쌍 안의 "원자"의 총 개수로 셉니다.
Example
$A(x) = \sum\limits_{i=0}^\infty 2^i x^i$가 각 돌이 $2$가지 색 중 하나로 칠해진 돌 묶음을 센다고 하고(따라서 크기가 $i$인 묶음은 $2^i$개 있습니다), $B(x) = \sum\limits_{j=0}^{\infty} 3^j x^j$가 각 돌이 $3$가지 색 중 하나로 칠해진 돌 묶음을 센다고 합시다. 그러면 $C(x) = A(x) B(x) = \sum\limits_{k=0}^\infty c_k x^k$는 $c_k$에 대해 "돌 묶음 두 개로, 첫 번째 묶음은 유형 $A$의 돌로만, 두 번째 묶음은 유형 $B$의 돌로만 이루어지며, 돌의 총 개수가 $k$인 것"으로 묘사할 수 있는 대상들을 셉니다.
비슷한 방식으로, 형식적 멱급수에 대한 다른 몇몇 함수에도 직관적인 의미가 있습니다.
다항식의 긴 나눗셈¶
정수와 마찬가지로, 다항식에서도 긴 나눗셈을 정의할 수 있습니다.
정의
임의의 다항식 $A$와 $B \neq 0$에 대해, $A$를 다음과 같이 나타낼 수 있습니다
여기서 $R$은 $A$를 $B$로 나눈 나머지라고 하고, $D$는 몫이라고 합니다.
$\deg A = n$, $\deg B = m$이라고 할 때, 이를 구하는 단순한 방법은 긴 나눗셈을 사용하는 것으로, $A$의 차수가 $B$의 차수보다 작아질 때까지 $B$에 단항식 $\frac{a_n}{b_m} x^{n - m}$을 곱하여 $A$에서 빼는 과정을 반복합니다. 마지막에 $A$에 남는 것이 나머지가 되며(그래서 이런 이름이 붙었습니다), 이 과정에서 $B$에 곱했던 다항식들을 모두 더한 것이 몫이 됩니다.
정의
$A$와 $B$를 $C$로 나눈 나머지가 같으면 $A$와 $B$는 $C$를 법으로 합동이라고 하며, 이는 다음과 같이 표기합니다.
다항식 나눗셈은 여러 중요한 성질을 가지고 있어 유용합니다.
-
$A$가 $B$의 배수일 필요충분조건은 $A \equiv 0 \pmod B$입니다.
-
이는 $A \equiv B \pmod C$일 필요충분조건이 $A-B$가 $C$의 배수라는 것임을 의미합니다.
-
특히 $A \equiv B \pmod{C \cdot D}$이면 $A \equiv B \pmod{C}$가 성립합니다.
-
임의의 일차 다항식 $x-r$에 대해 $A(x) \equiv A(r) \pmod{x-r}$이 성립합니다.
-
이는 $A$가 $x-r$의 배수일 필요충분조건이 $A(r)=0$임을 의미합니다.
-
법이 $x^k$인 경우 $A \equiv a_0 + a_1 x + \dots + a_{k-1} x^{k-1} \pmod{x^k}$이 성립합니다.
형식적 멱급수에 대해서는 나눗셈을 제대로 정의할 수 없다는 점에 유의하십시오. 그 대신 $a_0 \neq 0$인 임의의 $A(x)$에 대해 $A(x) A^{-1}(x) = 1$을 만족하는 역 형식적 멱급수 $A^{-1}(x)$를 정의할 수 있습니다. 그리고 이 사실을 이용하여 다항식 나눗셈의 결과를 계산할 수 있습니다.
기본 구현¶
여기에서 다항식 대수의 기본 구현을 찾을 수 있습니다.
이 구현은 모든 기본적인 연산과 그 밖의 몇 가지 유용한 메서드를 지원합니다. 주요 클래스는 T 타입의 계수를 갖는 다항식을 위한 poly<T>입니다.
모든 산술 연산 +, -, *, %, /를 지원하며, %와 /는 유클리드 나눗셈의 나머지와 몫을 나타냅니다.
소수 m을 법으로 하는 나머지에 대해 산술 연산을 수행하기 위한 modular<m> 클래스도 있습니다.
그 밖의 유용한 함수는 다음과 같습니다.
deriv(): $P(x)$의 도함수 $P'(x)$를 계산합니다.integr(): $Q(0)=0$을 만족하는 $P(x)$의 부정적분 $Q(x) = \int P(x)$를 계산합니다.inv(size_t n): $P^{-1}(x)$의 처음 $n$개 계수를 $O(n \log n)$에 계산합니다.log(size_t n): $\ln P(x)$의 처음 $n$개 계수를 $O(n \log n)$에 계산합니다.exp(size_t n): $\exp P(x)$의 처음 $n$개 계수를 $O(n \log n)$에 계산합니다.pow(size_t k, size_t n): $P^{k}(x)$의 처음 $n$개 계수를 $O(n \log nk)$에 계산합니다.deg(): $P(x)$의 차수를 반환합니다.lead(): $x^{\deg P(x)}$의 계수를 반환합니다.resultant(poly<T> a, poly<T> b): $a$와 $b$의 종결식을 $O(|a| \cdot |b|)$에 계산합니다.bpow(T x, size_t n): $x^n$을 계산합니다.bpow(T x, size_t n, T m): $x^n \pmod{m}$을 계산합니다.chirpz(T z, size_t n): $P(1), P(z), P(z^2), \dots, P(z^{n-1})$을 $O(n \log n)$에 계산합니다.vector<T> eval(vector<T> x): $P(x_1), \dots, P(x_n)$을 $O(n \log^2 n)$에 계산합니다.poly<T> inter(vector<T> x, vector<T> y): $P(x_i) = y_i$인 쌍들의 집합으로부터 다항식을 $O(n \log^2 n)$에 보간합니다.- 이 밖에도 더 있으니 코드를 자유롭게 살펴보십시오!
산술 연산¶
곱셈¶
가장 핵심이 되는 연산은 두 다항식의 곱셈입니다. 즉, 다항식 $A$와 $B$가 주어졌을 때:
다음과 같이 정의되는 다항식 $C = A \cdot B$를 계산해야 합니다
이는 고속 푸리에 변환을 통해 $O(n \log n)$에 계산할 수 있으며, 여기서 다루는 거의 모든 방법이 이를 서브루틴으로 사용합니다.
역급수¶
$A(0) \neq 0$이면 $A^{-1} A = 1$을 만족하는 무한 형식적 멱급수 $A^{-1}(x) = q_0+q_1 x + q_2 x^2 + \dots$가 항상 존재합니다. $A^{-1}$의 처음 $k$개 계수를 계산하는 것(즉, $x^k$를 법으로 하여 계산하는 것)이 유용한 경우가 많습니다. 이를 계산하는 주요 방법은 두 가지입니다.
분할 정복¶
이 알고리즘은 Schönhage의 논문에서 언급되었으며 Graeffe의 방법에서 영감을 받았습니다. $B(x)=A(x)A(-x)$에 대해 $B(x)=B(-x)$가 성립한다는 것, 즉 $B(x)$가 짝다항식이라는 것이 알려져 있습니다. 이는 짝수 번째 계수만 0이 아닌 값을 가질 수 있으며, $B(x)=T(x^2)$로 나타낼 수 있다는 뜻입니다. 따라서 다음과 같은 전이를 수행할 수 있습니다:
$T(x)$는 한 번의 곱셈으로 계산할 수 있으며, 그 이후에는 그 역급수의 계수 중 앞쪽 절반에만 관심을 두면 된다는 점에 유의하십시오. 이렇게 하면 $A^{-1} \pmod{x^k}$를 계산하는 원래 문제가 사실상 $T^{-1} \pmod{x^{\lceil k / 2 \rceil}}$를 계산하는 문제로 축소됩니다.
이 방법의 복잡도는 다음과 같이 추정할 수 있습니다
Sieveking–Kung 알고리즘¶
여기서 설명하는 일반적인 과정은 Hensel의 보조정리에서 비롯되므로 Hensel 리프팅이라고 알려져 있습니다. 이에 대해서는 아래에서 더 자세히 다루겠지만, 지금은 이 문제에 특화된 풀이에 집중합시다. 여기서 "리프팅"이란 $A^{-1} \pmod x$인 근삿값 $B_0=q_0=a_0^{-1}$에서 시작하여 $\bmod x^a$에서 $\bmod x^{2a}$로 반복적으로 끌어올린다는 뜻입니다.
$B_k \equiv A^{-1} \pmod{x^a}$라고 합시다. 다음 근삿값은 방정식 $A B_{k+1} \equiv 1 \pmod{x^{2a}}$를 만족해야 하며, $B_{k+1} = B_k + x^a C$로 나타낼 수 있습니다. 이로부터 다음 방정식이 도출됩니다
$A B_k \equiv 1 + x^a D \pmod{x^{2a}}$라고 하면, 위 방정식으로부터 다음이 성립합니다
이로부터 최종 공식을 얻을 수 있으며, 그 공식은 다음과 같습니다
따라서 $B_0 \equiv a_0^{-1} \pmod x$에서 시작하여 $AB_k \equiv 1 \pmod{x^{2^k}}$를 만족하는 수열 $B_k$를 다음 복잡도로 계산합니다
이 알고리즘은 첫 번째 알고리즘보다 조금 더 복잡해 보일 수 있지만, 그 이면에는 매우 탄탄하고 실용적인 논리가 있으며, 다른 관점에서 바라보면 일반화할 여지도 매우 큽니다. 이에 대해서는 아래에서 설명하겠습니다.
유클리드 나눗셈¶
차수가 각각 $n$과 $m$인 두 다항식 $A(x)$와 $B(x)$를 생각해 봅시다. 앞서 말했듯이 $A(x)$는 다음과 같이 다시 쓸 수 있습니다.
$n \geq m$이라고 하면 $\deg D = n - m$이고, $A$의 최고차 $n-m+1$개 계수는 $R$에 영향을 주지 않습니다. 즉, 이를 연립방정식으로 보면 $A(x)$와 $B(x)$의 최고차 $n-m+1$개 계수로부터 $D(x)$를 복원할 수 있습니다.
여기서 말하는 연립일차방정식은 다음과 같은 형태로 쓸 수 있습니다.
이 형태를 보면, 역순 다항식을 다음과 같이 도입할 때
연립방정식을 다음과 같이 다시 쓸 수 있다는 결론을 얻습니다.
이로부터 $D(x)$의 모든 계수를 유일하게 복원할 수 있습니다.
그리고 이로부터 다시 $R(x)$를 $R(x) = A(x) - B(x)D(x)$로 복원할 수 있습니다.
위의 행렬은 이른바 삼각 퇴플리츠 행렬이며, 여기서 보듯이 임의의 퇴플리츠 행렬로 이루어진 연립일차방정식을 푸는 것은 사실상 다항식의 역원을 구하는 것과 동치라는 점에 유의하십시오. 더 나아가 그 역행렬 또한 삼각 퇴플리츠 행렬이며, 그 성분은 위에서 사용한 표현으로 나타내면 $(B^R(x))^{-1} \pmod{x^{n-m+1}}$의 계수입니다.
다항식의 함수 계산하기¶
뉴턴 방법¶
Sieveking–Kung 알고리즘을 일반화해 봅시다. $P(x)$는 다항식이어야 하고 $F(x)$는 다음과 같이 정의되는 어떤 다항식 값 함수일 때, 방정식 $F(P) = 0$을 생각해 봅시다.
여기서 $\beta$는 어떤 상수입니다. 새로운 형식 변수 $y$를 도입하면 $F(x)$를 다음과 같이 표현할 수 있음을 증명할 수 있습니다.
여기서 $F'(x)$는 다음과 같이 정의되는 도함수 형식적 멱급수이고,
$G(x, y)$는 $x$와 $y$에 대한 어떤 형식적 멱급수입니다. 이 결과를 이용하면 해를 반복적으로 구할 수 있습니다.
$F(Q_k) \equiv 0 \pmod{x^{a}}$라고 합시다. $F(Q_{k+1}) \equiv 0 \pmod{x^{2a}}$를 만족하는 $Q_{k+1} \equiv Q_k + x^a C \pmod{x^{2a}}$를 찾아야 합니다.
위 식에 $x = Q_{k+1}$과 $y=Q_k$를 대입하면 다음을 얻습니다.
$Q_{k+1} - Q_k \equiv 0 \pmod{x^a}$이므로 $(Q_{k+1} - Q_k)^2 \equiv 0 \pmod{x^{2a}}$도 성립하며, 따라서
마지막 식으로부터 $Q_{k+1}$의 값을 얻습니다.
따라서 다항식의 역원을 구하는 방법과 $F(Q_k)$를 계산하는 방법을 알면, $P$의 계수 $n$개를 다음 복잡도로 구할 수 있습니다.
여기서 $f(n)$은 $F(Q_k)$와 $F'(Q_k)^{-1}$를 계산하는 데 필요한 시간이며, 보통 $O(n \log n)$입니다.
위의 반복 규칙은 수치 해석에서 뉴턴 방법으로 알려져 있습니다.
헨젤의 보조정리¶
앞서 언급했듯이, 이 결과는 형식적이고 일반적인 형태로 헨젤의 보조정리로 알려져 있으며, 실제로 중첩된 환의 열을 다룰 때 훨씬 더 넓은 의미로 사용될 수 있습니다. 이 특정한 경우에는 $x$, $x^2$, $x^3$ 등을 법으로 하는 다항식 나머지의 수열을 다루었습니다.
Hensel의 리프팅이 유용하게 쓰일 수 있는 또 다른 예로는 이른바 p진수가 있습니다. p진수에서는 사실상 $p$, $p^2$, $p^3$ 등을 법으로 하는 정수 나머지들의 수열을 다룹니다. 예를 들어, 뉴턴 방법을 사용하면 주어진 진법에서 가능한 모든 자기형 수(제곱했을 때 끝자리가 자기 자신이 되는 수)를 찾을 수 있습니다. 이 문제는 독자의 연습 문제로 남겨 둡니다. 여러분의 풀이가 $10$진수에 대해 올바르게 동작하는지 확인하려면 이 문제를 풀어 보십시오.
로그¶
함수 $\ln P(x)$에 대해 다음이 알려져 있습니다:
따라서 $\ln P(x)$의 계수 $n$개를 $O(n \log n)$에 계산할 수 있습니다.
역급수¶
알고 보면 뉴턴 방법을 사용하여 $A^{-1}$에 대한 공식을 얻을 수 있습니다. 이를 위해 방정식 $A=Q^{-1}$을 취하면 다음과 같습니다:
지수¶
$e^{P(x)}=Q(x)$를 계산하는 방법을 알아봅시다. $\ln Q = P$가 성립해야 하므로 다음과 같습니다:
$k$제곱¶
이제 $P^k(x)=Q$를 계산해야 합니다. 이는 다음 공식을 통해 할 수 있습니다:
다만, 어떤 초기값 $Q_0$을 찾을 수 있을 때에만 로그와 지수를 올바르게 계산할 수 있다는 점에 유의하십시오.
이를 찾으려면 다항식의 상수항 계수의 로그 또는 지수를 계산해야 합니다.
그러나 이를 합리적으로 할 수 있는 경우는 $Q = \ln P$에 대해 $P(0)=1$이어서 $Q(0)=0$인 경우와, $Q = e^P$에 대해 $P(0)=0$이어서 $Q(0)=1$인 경우뿐입니다.
따라서 위 공식은 $P(0) = 1$인 경우에만 사용할 수 있습니다. 그렇지 않고 $T(0)=1$인 $P(x) = \alpha x^t T(x)$ 꼴이라면 다음과 같이 쓸 수 있습니다:
$\sqrt[k]{\alpha}$를 계산할 수 있다면(예를 들어 $\alpha=1$인 경우) 다항식의 $k$제곱근도 계산할 수 있다는 점에 유의하십시오.
값 계산과 보간¶
Chirp-z 변환¶
점 $x_r = z^{2r}$에서 다항식의 값을 계산해야 하는 특수한 경우에는 다음과 같이 할 수 있습니다:
$2kr = r^2+k^2-(r-k)^2$를 대입해 봅시다. 그러면 이 합은 다음과 같이 다시 쓸 수 있습니다:
이는 인수 $z^{r^2}$를 제외하면 수열 $u_k = a_k z^{k^2}$와 $v_k = z^{-k^2}$의 합성곱과 같습니다.
여기서 $u_k$의 인덱스는 $0$부터 $n$까지이고, $v_k$의 인덱스는 $-n$부터 $m$까지라는 점에 유의하십시오. 이때 $m$은 필요한 $z$의 최대 거듭제곱 지수입니다.
이제 점 $x_r = z^{2r+1}$에서 다항식의 값을 계산해야 한다면, 변환 $a_k \to a_k z^k$를 통해 이전 문제로 환원할 수 있습니다.
이를 통해 $z$의 거듭제곱들에서 값을 계산해야 할 때 $O(n \log n)$ 알고리즘을 얻을 수 있으므로, 길이가 2의 거듭제곱이 아닌 경우에도 DFT를 계산할 수 있습니다.
또 다른 관찰은 $kr = \binom{k+r}{2} - \binom{k}{2} - \binom{r}{2}$라는 점입니다. 그러면 다음을 얻습니다.
다항식 $A_0(x) = \sum\limits_{k=0}^n a_{n-k}z^{-\binom{n-k}{2}}x^k$와 $A_1(x) = \sum\limits_{k\geq 0}z^{\binom{k}{2}}x^k$의 곱에서 $x^{n+r}$의 계수는 $z^{\binom{r}{2}}A(z^r)$와 같습니다. $A_0(x)$와 $A_1(x)$의 계수를 계산할 때 공식 $z^{\binom{k+1}{2}}=z^{\binom{k}{2}+k}$를 사용할 수 있습니다.
다중 점 평가¶
$A(x_1), \dots, A(x_n)$을 계산해야 한다고 가정합시다. 앞서 언급했듯이 $A(x) \equiv A(x_i) \pmod{x-x_i}$입니다. 따라서 다음과 같이 할 수 있습니다.
- 구간 $[l,r)$에 곱 $P_{l, r}(x) = (x-x_l)(x-x_{l+1})\dots(x-x_{r-1})$이 저장되도록 세그먼트 트리를 계산하십시오.
- 루트 노드에서 $l=1$, $r=n+1$로 시작합니다. $m=\lfloor(l+r)/2\rfloor$라고 합시다. 다항식 $A(x) \pmod{P_{l,m}(x)}$를 가지고 $[l,m)$으로 내려갑시다.
- 이렇게 하면 $A(x_l), \dots, A(x_{m-1})$이 재귀적으로 계산되며, 이제 $A(x) \pmod{P_{m,r}(x)}$를 가지고 $[m,r)$에 대해서도 같은 작업을 수행하십시오.
- 첫 번째와 두 번째 재귀 호출의 결과를 이어 붙여 반환하십시오.
전체 과정은 $O(n \log^2 n)$에 동작합니다.
보간¶
쌍 $(x_i, y_i)$의 집합이 주어졌을 때 다항식을 보간하는 Lagrange의 직접적인 공식이 있습니다.
이를 직접 계산하는 것은 어렵지만, 분할 정복 방식을 사용하면 $O(n \log^2 n)$에 계산할 수 있음이 밝혀졌습니다.
$P(x) = (x-x_1)\dots(x-x_n)$을 생각해 봅시다. $A(x)$에서 분모의 계수를 알려면 다음과 같은 곱을 계산해야 합니다.
그런데 도함수 $P'(x)$를 생각해 보면 $P'(x_i) = P_i$임을 알 수 있습니다. 따라서 $P_i$들을 평가를 통해 $O(n \log^2 n)$에 계산할 수 있습니다.
이제 다중 점 평가에서와 같은 세그먼트 트리 위에서 수행되는 재귀 알고리즘을 생각해 봅시다. 이 알고리즘은 각 리프에 값 $\dfrac{y_i}{P_i}$를 둔 상태로 리프에서 시작합니다.
재귀에서 돌아올 때 왼쪽과 오른쪽 정점의 결과를 $A_{l,r} = A_{l,m}P_{m,r} + P_{l,m} A_{m,r}$와 같이 병합해야 합니다.
이렇게 하면 루트로 돌아왔을 때 루트에 정확히 $A(x)$가 있게 됩니다. 전체 과정 역시 $O(n \log^2 n)$에 동작합니다.
최대공약수와 종결식¶
다항식 $A(x) = a_0 + a_1 x + \dots + a_n x^n$과 $B(x) = b_0 + b_1 x + \dots + b_m x^m$이 주어졌다고 가정합시다.
중복도를 포함하여 $\lambda_0, \dots, \lambda_n$을 $A(x)$의 근, $\mu_0, \dots, \mu_m$을 $B(x)$의 근이라고 합시다.
$A(x)$와 $B(x)$가 공통근을 가지는지 알고 싶다고 합시다. 이를 확인하는 서로 연관된 두 가지 방법이 있습니다.
유클리드 알고리즘¶
이에 대해서는 이미 글이 있습니다. 임의의 정역에서 유클리드 알고리즘은 다음과 같이 간단하게 작성할 수 있습니다:
template<typename T>
T gcd(const T &a, const T &b) {
return b == T(0) ? a : gcd(b, a % b);
}
다항식 $A(x)$와 $B(x)$에 대해 이 알고리즘이 $O(nm)$에 동작함을 증명할 수 있습니다.
종결식¶
곱 $A(\mu_0)\cdots A(\mu_m)$을 계산해 봅시다. 이 값은 어떤 $\mu_i$가 $A(x)$의 근일 때, 그리고 오직 그때에만 0이 됩니다.
대칭성을 위해 여기에 $b_m^n$을 곱하여 전체 곱을 다음 형태로 다시 쓸 수도 있습니다:
위에서 정의한 값을 다항식 $A(x)$와 $B(x)$의 종결식이라고 합니다. 정의로부터 다음 성질들을 알 수 있습니다:
- $\mathcal R(A, B) = (-1)^{nm} \mathcal R(B, A)$.
- $n=0$ 또는 $m=0$일 때 $\mathcal R(A, B)= a_n^m b_m^n$입니다.
- $b_m=1$이면 임의의 다항식 $C(x)$와 $n,m \geq 1$에 대해 $\mathcal R(A - CB, B) = \mathcal R(A, B)$입니다.
- 이로부터 임의의 $A(x)$, $B(x)$, $C(x)$에 대해 $\mathcal R(A, B) = b_m^{\deg(A) - \deg(A-CB)}\mathcal R(A - CB, B)$가 성립합니다.
놀랍게도 이는 두 다항식의 종결식이 실제로 항상 그 계수들과 같은 환에 속한다는 것을 의미합니다!
또한 이 성질들을 이용하면 $O(nm)$에 동작하는 유클리드 알고리즘과 함께 종결식을 계산할 수 있습니다.
template<typename T>
T resultant(poly<T> a, poly<T> b) {
if(b.is_zero()) {
return 0;
} else if(b.deg() == 0) {
return bpow(b.lead(), a.deg());
} else {
int pw = a.deg();
a %= b;
pw -= a.deg();
base mul = bpow(b.lead(), pw) * base((b.deg() & a.deg() & 1) ? -1 : 1);
base ans = resultant(b, a);
return ans * mul;
}
}
Half-GCD 알고리즘¶
GCD와 종결식을 $O(n \log^2 n)$에 계산하는 방법이 있습니다.
이를 위한 절차는 다항식 쌍 $a(x)$, $b(x)$를 $\deg d(x) \leq \frac{\deg a(x)}{2}$를 만족하는 다른 쌍 $c(x), d(x)$로 옮기는 $2 \times 2$ 선형 변환을 구현합니다. 충분히 주의를 기울이면, 크기가 적어도 $2$배 작은 다항식들에 대한 최대 $2$번의 재귀 호출로 임의의 다항식 쌍의 half-GCD를 계산할 수 있습니다.
알고리즘의 구체적인 세부 사항은 설명하기가 다소 번거롭지만, 라이브러리에서 half_gcd 함수로 구현된 것을 찾을 수 있습니다.
half-GCD를 구현한 뒤에는 $\gcd(a, b)$와 $0$의 쌍으로 줄어들 때까지 다항식에 이를 반복해서 적용할 수 있습니다.