Polynomial Library

Polynomial 관련 라이브러리입니다.

• Polynomial은 $\sum_{i=0}^d a_i x^i$로 표현되며, $a$에 해당하는 길이 $d+1$의 배열을 내부에 가지고 있습니다.
• Polynomial은 Field $F$위에서 정의되며, $\vec{a}$와 $\vec{b}$의 convolution을 계산하는 함수를 제공해야합니다.
  • 아래에서, convolution을 계산하는 함수의 시간복잡도가 길이가 $d$인 경우 $O(d \log d)$라고 가정합니다.
• 생성자
  • 인자가 없으면 빈 다항식을 생성합니다.
  • vector<F>를 인자로 주는 경우, $i$번째 원소를 $a_i$로 하는 다항식을 생성합니다.
• int deg(), void set_degree (int deg)
  
  • 차수에 관한 함수입니다. $f = 0$은 차수 $-1$로 표현합니다.
  • 최고차항의 계수가 $0$일 수 있습니다.
  • deg()는 $O(1)$, set_degree는 $O(d+\texttt{deg})$ 시간이 걸립니다.
• operator[] (int idx)
  • $a_{\texttt{idx}}$를 반환합니다.
  • $O(1)$ 시간이 걸립니다.
• operator+, operator+=, operator-, operator-=
  • 두 다항식을 더하고 뺍니다. 차수는 두 다항식의 최댓값입니다.
  • $O(d)$ 시간이 걸립니다.
• unary operator-
  • $-f$를 반환합니다. 차수는 동일합니다
  • $O(d)$ 시간이 걸립니다.
• operator*, operator*=
  • 두 다항식을 곱합니다. 차수는 두 다항식의 합이지만, 어느 한쪽의 차수가 $-1$인 경우 $-1$입니다.
  • $O(d \log d)$ 시간이 걸립니다.
• Polynomial inv(int degree = -1) const
  
  • $1/f(x)$의 푸리에 전개를 degree차수까지 구합니다. 기본값은 deg()입니다.
  • $f(0) \ne 0$일 필요가 있습니다.
  • $O(inv + d \log d)$ 시간이 걸립니다.
• Polynomial integ() const
  • $\int_0^x f(t) dt$를 구합니다. 차수가 $1$ 늘어난 다항식이 반환됩니다.
  • $O(d \cdot inv)$ 시간이 걸립니다.
• Polynomial diff() const
  • $df/dt$를 구합니다. 차수가 $1$ 줄어든 다항식이 반환됩니다.
  • $O(d)$ 시간이 걸립니다.
• Polynomial ln(int degree = -1) const
  • $\ln f(x)$의 푸리에 전개를 degree차수까지 구합니다. 기본값은 deg()입니다.
  • $f(0) = 1$일 필요가 있습니다.
  • $O(d (inv + \log d))$ 시간이 걸립니다.
• Polynomial exp(int degree = -1) const
  • $\exp f(x)$의 푸리에 전개를 degree차수까지 구합니다. 기본값은 deg()입니다.
  • $f(0) = 0$일 필요가 있습니다.
  • $O(d (inv + \log d))$ 시간이 걸립니다.
• Polynomial taylor_shift(F a) const
  • $f(x+a)$를 구합니다. 차수는 동일합니다.
  • $O(d (inv + \log d))$ 시간이 걸립니다.
• Polynomial floordiv_xK(int K) const
  • $f(x)/x^K$에서, $x^{-1}$ 아래의 항을 무시한 값을 구합니다.
  • 차수가 $K$줄어듭니다.
  • $O(d)$ 시간이 걸립니다.
• 개선점 / 추가 예정 사항
  
  • $F$ 사이의 나눗셈의 시간이 오래 걸리는 경우를 개선하고자 합니다.
  • $f, g$가 주어졌을 때, 몫과 나머지를 구하는 함수를 만들고자 합니다.
    • $f = qg+r (\deg r < \deg g)$
  • $x^K$를 곱하는 함수를 추가하고, 쉬프트 연산자 오버로딩을 추가하고자 합니다.
  • 함수를 Evaluate하고, Multipoint Evaluation을 계산하는 로직을 만들고자 합니다.
  • 함수의 $K$ 제곱을 추가하고자 합니다.
  • 함수의 합성을 추가하고자 합니다.
  • $\sqrt{f}$의 테일러 전개를 추가하고자 합니다.
  • FFT가 정확한 경우, inv의 실행시간을 개선하고자 합니다.

 

poly.cpp

0.01MB