Агуулгыг алгасах

Олон гишүүнт ба цуваан дээрх үйлдлүүд

Программчлалын тэмцээний бодлого, ялангуяа ямар нэг тоолол агуулсан бодлогуудыг олон гишүүнт ба формал зэрэгт цуваан дээр ямар нэг зүйл тооцоолох бодлого болгон шилжүүлж бодох нь элбэг.

Үүнд олон гишүүнт үржүүлэх, интерполяц зэрэг ойлголт, түүнчлэн олон гишүүнтийн логарифм, экспонент зэрэг илүү нийлмэл ойлголтууд багтана. Энэ өгүүлэлд ийм үйлдлүүд болон тэдгээрт хандах түгээмэл аргуудын товч тоймыг танилцуулна.

Үндсэн ойлголт ба баримтууд

Энэ хэсэгт бид олон гишүүнтийн янз бүрийн үйлдлийн тодорхойлолт ба "зөн совингийн" шинж чанарт илүү анхаарна. Тэдгээрийн хэрэгжүүлэлтийн техникийн нарийн ширийн зүйл ба complexity-г дараагийн хэсгүүдэд авч үзнэ.

Олон гишүүнт үржүүлэх

Тодорхойлолт

Нэг хувьсагчтай олон гишүүнт гэдэг нь $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$ гэж үзнэ.

Тодорхойлолт

Хоёр олон гишүүнтийн үржвэр-ийг арифметик илэрхийлэл мэт задлах замаар тодорхойлно:

$$ A(x) B(x) = \left(\sum\limits_{i=0}^n a_i x^i \right)\left(\sum\limits_{j=0}^m b_j x^j\right) = \sum\limits_{i,j} a_i b_j x^{i+j} = \sum\limits_{k=0}^{n+m} c_k x^k = C(x). $$

$C(x)$-ийн коэффициентүүдийн $c_0, c_1, \dots, c_{n+m}$ дарааллыг $a_0, \dots, a_n$ ба $b_0, \dots, b_m$-ийн convolution гэж нэрлэдэг.

Тодорхойлолт

$a_n \neq 0$ байх $A$ олон гишүүнтийн зэрэг-ийг $\deg A = n$ гэж тодорхойлно.

Тууштай байдлын үүднээс $A(x) = 0$-ийн зэргийг $\deg A = -\infty$ гэж тодорхойлно.

Энэ утгаараа дурын $A$ ба $B$ олон гишүүнтийн хувьд $\deg AB = \deg A + \deg B$ болно.

Convolution нь олон тооллын бодлого бодох үндэс суурь юм.

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)$ формал зэрэгт цувааны үржвэр-ийг мөн арифметик илэрхийлэл мэт задлах замаар тодорхойлно:

$$ A(x) B(x) = \left(\sum\limits_{i=0}^\infty a_i x^i \right)\left(\sum\limits_{j=0}^\infty b_j x^j\right) = \sum\limits_{i,j} a_i b_j x^{i+j} = \sum\limits_{k=0}^{\infty} c_k x^k = C(x), $$

энд $c_0, c_1, \dots$ коэффициентүүдийг төгсгөлөг нийлбэр хэлбэрээр тодорхойлно

$$ c_k = \sum\limits_{i=0}^k a_i b_{k-i}. $$

$c_0, c_1, \dots$ дарааллыг мөн $a_0, a_1, \dots$ ба $b_0, b_1, \dots$-ийн convolution гэж нэрлэх ба ингэснээр ойлголтыг төгсгөлгүй дараалалд ерөнхийлнө.

Тиймээс олон гишүүнтийг формал зэрэгт цуваа гэж үзэж болох ч төгсгөлөг тооны коэффициенттэй.

Формал зэрэгт цуваа нь тооллын комбинаторикт чухал үүрэг гүйцэтгэдэг бөгөөд тэнд тэдгээрийг янз бүрийн дарааллын үүсгэгч функц болгон судалдаг. Үүсгэгч функц болон тэдгээрийн ард байгаа зөн совингийн дэлгэрэнгүй тайлбар нь харамсалтай нь энэ өгүүллийн хүрээнээс гадуур байх тул сониуч уншигчийг тэдгээрийн комбинаторикийн утгын талаар дэлгэрэнгүй мэдэхийн тулд жишээ нь энд хандахыг зөвлөе.

Гэвч бид маш товчхон дурдахад хэрэв $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$-г дараах байдлаар илэрхийлж болно

$$ A = D \cdot B + R,~ \deg R < \deg B, $$

энд $R$-г $B$ модулиар $A$-гийн үлдэгдэл, $D$-г ноогдвор гэж нэрлэнэ.

$\deg A = n$ ба $\deg B = m$ гэж тэмдэглэвэл үүнийг хийх энгийн арга бол урт хуваалт ашиглах явдал бөгөөд үүний явцад та $B$-г $\frac{a_n}{b_m} x^{n - m}$ нэг гишүүнтээр үржүүлж, $A$-гийн зэрэг $B$-ийнхээс бага болтол $A$-аас хасна. Эцэст нь $A$-аас юу үлдэх нь үлдэгдэл (эндээс нэр нь гарсан) байх ба явцад $B$-г үржүүлсэн олон гишүүнтүүдийг нийлбэрлэвэл ноогдвор гарна.

Тодорхойлолт

Хэрэв $A$ ба $B$ нь $C$ модулиар ижил үлдэгдэлтэй бол тэдгээрийг $C$ модулиар эквивалент гэж хэлэх ба дараах байдлаар тэмдэглэнэ

$$ A \equiv B \pmod{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)$-г тодорхойлж болно. Энэ баримтыг эргээд олон гишүүнтийн урт хуваалтын үр дүнг тооцоолоход ашиглаж болно.

Basic implementation

Here you can find the basic implementation of polynomial algebra.

It supports all trivial operations and some other useful methods. The main class is poly<T> for polynomials with coefficients of type T.

All arithmetic operation +, -, *, % and / are supported, % and / standing for remainder and quotient in Euclidean division.

There is also the class modular<m> for performing arithmetic operations on remainders modulo a prime number m.

Other useful functions:

  • deriv(): computes the derivative $P'(x)$ of $P(x)$.
  • integr(): computes the indefinite integral $Q(x) = \int P(x)$ of $P(x)$ such that $Q(0)=0$.
  • inv(size_t n): calculate the first $n$ coefficients of $P^{-1}(x)$ in $O(n \log n)$.
  • log(size_t n): calculate the first $n$ coefficients of $\ln P(x)$ in $O(n \log n)$.
  • exp(size_t n): calculate the first $n$ coefficients of $\exp P(x)$ in $O(n \log n)$.
  • pow(size_t k, size_t n): calculate the first $n$ coefficients for $P^{k}(x)$ in $O(n \log nk)$.
  • deg(): returns the degree of $P(x)$.
  • lead(): returns the coefficient of $x^{\deg P(x)}$.
  • resultant(poly<T> a, poly<T> b): computes the resultant of $a$ and $b$ in $O(|a| \cdot |b|)$.
  • bpow(T x, size_t n): computes $x^n$.
  • bpow(T x, size_t n, T m): computes $x^n \pmod{m}$.
  • chirpz(T z, size_t n): computes $P(1), P(z), P(z^2), \dots, P(z^{n-1})$ in $O(n \log n)$.
  • vector<T> eval(vector<T> x): evaluates $P(x_1), \dots, P(x_n)$ in $O(n \log^2 n)$.
  • poly<T> inter(vector<T> x, vector<T> y): interpolates a polynomial by a set of pairs $P(x_i) = y_i$ in $O(n \log^2 n)$.
  • And some more, feel free to explore the code!

Арифметик

Үржүүлэх

Хамгийн гол үйлдэл бол хоёр олон гишүүнтийг үржүүлэх явдал юм. Өөрөөр хэлбэл $A$ ба $B$ олон гишүүнт өгөгдсөн үед:

$$A = a_0 + a_1 x + \dots + a_n x^n$$
$$B = b_0 + b_1 x + \dots + b_m x^m$$

Та дараах байдлаар тодорхойлогдох $C = A \cdot B$ олон гишүүнтийг тооцоолох ёстой

$$\boxed{C = \sum\limits_{i=0}^n \sum\limits_{j=0}^m a_i b_j x^{i+j}} = c_0 + c_1 x + \dots + c_{n+m} x^{n+m}.$$

Үүнийг Хурдан Фурье хувиргалт-аар $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$ модулиар тооцоолох) нь ихэвчлэн хэрэгтэй байдаг. Үүнийг тооцоолох хоёр үндсэн арга бий.

Хуваа ба ялагтун

Энэ алгоритмыг Шёнхагегийн өгүүлэлд дурдсан бөгөөд Греффегийн арга-аас санаа авсан. $B(x)=A(x)A(-x)$-ийн хувьд $B(x)=B(-x)$ биелдэг нь мэдэгдэж байгаа, өөрөөр хэлбэл $B(x)$ нь тэгш олон гишүүнт юм. Энэ нь түүнд зөвхөн тэгш дугаартай тэгээс ялгаатай коэффициент байх ба $B(x)=T(x^2)$ хэлбэрээр илэрхийлж болно гэсэн үг. Тиймээс бид дараах шилжилтийг хийж болно:

$$A^{-1}(x) \equiv \frac{1}{A(x)} \equiv \frac{A(-x)}{A(x)A(-x)} \equiv \frac{A(-x)}{T(x^2)} \pmod{x^k}$$

$T(x)$-г ганц үржүүлэлтээр тооцоолж болох ба үүний дараа бид зөвхөн түүний урвуу цувааны коэффициентүүдийн эхний хагаст сонирхолтой байгааг анхаараарай. Энэ нь $A^{-1} \pmod{x^k}$-г тооцоолох анхны бодлогыг $T^{-1} \pmod{x^{\lceil k / 2 \rceil}}$-г тооцоолох бодлого болгон үр дүнтэй хураана.

Энэ аргын complexity-г дараах байдлаар үнэлж болно

$$T(n) = T(n/2) + O(n \log n) = O(n \log n).$$

Сивекинг–Кунгийн алгоритм

Энд тайлбарласан ерөнхий процессыг Хензелийн өргөлт гэж нэрлэдэг бөгөөд энэ нь Хензелийн леммээс гардаг. Бид үүнийг доор илүү дэлгэрэнгүй авч үзэх ба одоохондоо тусгай шийдэлд анхаарлаа хандуулъя. Энд "өргөлт" гэдэг нь бид $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 + x^{a}C) \equiv 1 \pmod{x^{2a}}.$$

$A B_k \equiv 1 + x^a D \pmod{x^{2a}}$ гэвэл дээрх тэгшитгэл дараахыг илэрхийлнэ

$$x^a(D+AC) \equiv 0 \pmod{x^{2a}} \implies D \equiv -AC \pmod{x^a} \implies C \equiv -B_k D \pmod{x^a}.$$

Эндээс эцсийн томьёог гаргаж болно:

$$x^a C \equiv -B_k x^a D \equiv B_k(1-AB_k) \pmod{x^{2a}} \implies \boxed{B_{k+1} \equiv B_k(2-AB_k) \pmod{x^{2a}}}$$

Тиймээс $B_0 \equiv a_0^{-1} \pmod x$-ээс эхлэн бид $AB_k \equiv 1 \pmod{x^{2^k}}$ байх $B_k$ дарааллыг дараах complexity-тэйгээр тооцоолно

$$T(n) = T(n/2) + O(n \log n) = O(n \log n).$$

Энд байгаа алгоритм эхнийхээс арай төвөгтэй санагдаж болох ч түүний ард маш бат бөх, практик үндэслэл байгаа бөгөөд өөр өнцгөөс харвал доор тайлбарлах маш сайн ерөнхийлөх боломжтой.

Евклидийн хуваалт

$n$ ба $m$ зэрэгтэй $A(x)$ ба $B(x)$ хоёр олон гишүүнтийг авч үзье. Өмнө хэлсэнчлэн та $A(x)$-г дараах байдлаар дахин бичиж болно

$$A(x) = B(x) D(x) + R(x), \deg R < \deg B.$$

$n \geq m$ гэвэл энэ нь $\deg D = n - m$ болохыг илэрхийлэх ба $A$-гийн тэргүүлэх $n-m+1$ коэффициент нь $R$-д нөлөөлөхгүй. Энэ нь та үүнийг тэгшитгэлийн систем гэж үзвэл $A(x)$ ба $B(x)$-ийн хамгийн том $n-m+1$ коэффициентээс $D(x)$-г сэргээж чадна гэсэн үг.

Бидний ярьж буй шугаман тэгшитгэлийн системийг дараах хэлбэрээр бичиж болно:

$$\begin{bmatrix} a_n \\ \vdots \\ a_{m+1} \\ a_{m} \end{bmatrix} = \begin{bmatrix} b_m & \dots & 0 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ \dots & \dots & b_m & 0 \\ \dots & \dots & b_{m-1} & b_m \end{bmatrix} \begin{bmatrix}d_{n-m} \\ \vdots \\ d_1 \\ d_0\end{bmatrix}$$

Эндээс харахад урвуулсан олон гишүүнтүүдийг оруулснаар

$$A^R(x) = x^nA(x^{-1})= a_n + a_{n-1} x + \dots + a_0 x^n$$
$$B^R(x) = x^m B(x^{-1}) = b_m + b_{m-1} x + \dots + b_0 x^m$$
$$D^R(x) = x^{n-m}D(x^{-1}) = d_{n-m} + d_{n-m-1} x + \dots + d_0 x^{n-m}$$

системийг дараах байдлаар дахин бичиж болно гэж дүгнэж болно

$$A^R(x) \equiv B^R(x) D^R(x) \pmod{x^{n-m+1}}.$$

Эндээс та $D(x)$-ийн бүх коэффициентийг эргэлзээгүйгээр сэргээж болно:

$$\boxed{D^R(x) \equiv A^R(x) (B^R(x))^{-1} \pmod{x^{n-m+1}}}$$

Эндээс эргээд та $R(x)$-г $R(x) = A(x) - B(x)D(x)$ хэлбэрээр сэргээж болно.

Дээрх матриц нь гурвалжин Тёплицийн матриц гэж нэрлэгддэг зүйл бөгөөд энд харж байгаачлан дурын Тёплицийн матрицтай шугаман тэгшитгэлийн системийг бодох нь үнэндээ олон гишүүнт урвуулахтай эквивалент юм. Түүнчлэн түүний урвуу матриц нь мөн гурвалжин Тёплицийн матриц байх ба дээр хэрэглэсэн нэр томьёогоор түүний элементүүд нь $(B^R(x))^{-1} \pmod{x^{n-m+1}}$-ийн коэффициентүүд байна.

Олон гишүүнтийн функцийг тооцоолох

Ньютоны арга

Сивекинг–Кунгийн алгоритмыг ерөнхийлье. $F(P) = 0$ тэгшитгэлийг авч үзье, энд $P(x)$ нь олон гишүүнт байх ёстой бөгөөд $F(x)$ нь дараах байдлаар тодорхойлогдох олон гишүүнт утгатай функц юм

$$F(x) = \sum\limits_{i=0}^\infty \alpha_i (x-\beta)^i,$$

энд $\beta$ нь ямар нэг тогтмол. Хэрэв бид шинэ формал хувьсагч $y$ оруулбал $F(x)$-г дараах байдлаар илэрхийлж болохыг батлаж болно

$$F(x) = F(y) + (x-y)F'(y) + (x-y)^2 G(x,y),$$

энд $F'(x)$ нь дараах байдлаар тодорхойлогдох уламжлалын формал зэрэгт цуваа

$$F'(x) = \sum\limits_{i=0}^\infty (i+1)\alpha_{i+1}(x-\beta)^i,$$

мөн $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$ орлуулбал бид дараахыг авна

$$F(Q_{k+1}) \equiv F(Q_k) + (Q_{k+1} - Q_k) F'(Q_k) + (Q_{k+1} - Q_k)^2 G(x, y) \pmod x^{2a}.$$

$Q_{k+1} - Q_k \equiv 0 \pmod{x^a}$ тул $(Q_{k+1} - Q_k)^2 \equiv 0 \pmod{x^{2a}}$ мөн биелнэ, тиймээс

$$0 \equiv F(Q_{k+1}) \equiv F(Q_k) + (Q_{k+1} - Q_k) F'(Q_k) \pmod{x^{2a}}.$$

Сүүлийн томьёо нь бидэнд $Q_{k+1}$-ийн утгыг өгнө:

$$\boxed{Q_{k+1} = Q_k - \dfrac{F(Q_k)}{F'(Q_k)} \pmod{x^{2a}}}$$

Тиймээс олон гишүүнтийг хэрхэн урвуулах ба $F(Q_k)$-г хэрхэн тооцоолохыг мэдсэнээр бид $P$-ийн $n$ коэффициентийг дараах complexity-тэйгээр олж чадна

$$T(n) = T(n/2) + f(n),$$

энд $f(n)$ нь $F(Q_k)$ ба $F'(Q_k)^{-1}$-г тооцоолоход шаардагдах хугацаа бөгөөд ихэвчлэн $O(n \log n)$ байна.

Дээрх давталтын дүрмийг тоон шинжилгээнд Ньютоны арга гэж нэрлэдэг.

Хензелийн лемм

Өмнө дурдсанчлан албан ёсоор бөгөөд ерөнхийд нь энэ үр дүнг Хензелийн лемм гэж нэрлэдэг бөгөөд бид үүрлэсэн цагирагийн цувралтай ажиллах үед үүнийг бүр илүү өргөн утгаар ашиглаж болно. Энэ тохиолдолд бид $x$, $x^2$, $x^3$ гэх мэт модулиар олон гишүүнтийн үлдэгдлүүдийн дараалалтай ажилласан.

Хензелийн өргөлт хэрэгтэй байж болох өөр нэг жишээ бол p-адик тоо гэж нэрлэгддэг зүйл юм, тэнд бид үнэндээ $p$, $p^2$, $p^3$ гэх мэт модулиар бүхэл тооны үлдэгдлүүдийн дараалалтай ажилладаг. Жишээ нь Ньютоны аргыг ашиглан өгөгдсөн тооны суурьтай бүх боломжит автоморф тоо (квадрат авахад өөрөөрөө төгсдөг тоо)-г олж болно. Энэ бодлогыг уншигчид дасгал болгон үлдээе. Таны шийдэл $10$ суурьт тооны хувьд ажиллаж байгаа эсэхийг шалгахын тулд энэ бодлогыг авч үзэж болно.

Логарифм

$\ln P(x)$ функцийн хувьд дараах нь мэдэгдэж байгаа:

$$ \boxed{(\ln P(x))' = \dfrac{P'(x)}{P(x)}} $$

Тиймээс бид $\ln P(x)$-ийн $n$ коэффициентийг $O(n \log n)$-д тооцоолж болно.

Урвуу цуваа

Ньютоны аргыг ашиглан бид $A^{-1}$-ийн томьёог гаргаж чадна. Үүний тулд бид $A=Q^{-1}$ тэгшитгэлийг авна, тиймээс:

$$F(Q) = Q^{-1} - A$$
$$F'(Q) = -Q^{-2}$$
$$\boxed{Q_{k+1} \equiv Q_k(2-AQ_k) \pmod{x^{2^{k+1}}}}$$

Экспонент

$e^{P(x)}=Q(x)$-г тооцоолж сурцгаая. $\ln Q = P$ биелэх ёстой, тиймээс:

$$F(Q) = \ln Q - P$$
$$F'(Q) = Q^{-1}$$
$$\boxed{Q_{k+1} \equiv Q_k(1 + P - \ln Q_k) \pmod{x^{2^{k+1}}}}$$

$k$ дугаар зэрэг

Одоо бид $P^k(x)=Q$-г тооцоолох хэрэгтэй. Үүнийг дараах томьёогоор хийж болно:

$$Q = \exp\left[k \ln P(x)\right]$$

Гэвч та ямар нэг эхний $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)$ бол та дараах байдлаар бичиж болно:

$$\boxed{P^k(x) = \alpha^kx^{kt} \exp[k \ln T(x)]}$$

Хэрэв та $\sqrt[k]{\alpha}$-г тооцоолж чадвал, жишээ нь $\alpha=1$-ийн хувьд, олон гишүүнтийн ямар нэг $k$ дугаар язгуурыг мөн тооцоолж болно гэдгийг анхаараарай.

Утга олох ба интерполяц

Chirp-z хувиргалт

$x_r = z^{2r}$ цэгүүдэд олон гишүүнтийн утгыг олох шаардлагатай тусгай тохиолдолд та дараахыг хийж болно:

$$A(z^{2r}) = \sum\limits_{k=0}^n a_k z^{2kr}$$

$2kr = r^2+k^2-(r-k)^2$ гэж орлуулъя. Тэгвэл энэ нийлбэр дараах байдлаар дахин бичигдэнэ:

$$\boxed{A(z^{2r}) = z^{r^2}\sum\limits_{k=0}^n (a_k z^{k^2}) z^{-(r-k)^2}}$$

Энэ нь $z^{r^2}$ үржигдэхүүнийг эс тооцвол $u_k = a_k z^{k^2}$ ба $v_k = z^{-k^2}$ дарааллуудын convolution-тай тэнцүү юм.

Энд $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)$ алгоритм өгөх ба ингэснээр та хоёрын зэрэг биш утгын хувьд DFT-г тооцоолж болно.

Өөр нэг ажиглалт бол $kr = \binom{k+r}{2} - \binom{k}{2} - \binom{r}{2}$. Тэгвэл бидэнд

$$\boxed{A(z^r) = z^{-\binom{r}{2}}\sum\limits_{k=0}^n \left(a_k z^{-\binom{k}{2}}\right)z^{\binom{k+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}$. Тиймээс та дараахыг хийж болно:

  1. $[l,r)$ хэрчимд $P_{l, r}(x) = (x-x_l)(x-x_{l+1})\dots(x-x_{r-1})$ үржвэр байхаар хэрчмийн мод байгуул.
  2. Үндсэн оройд $l=1$ ба $r=n+1$-ээс эхэл. $m=\lfloor(l+r)/2\rfloor$ гэе. $A(x) \pmod{P_{l,m}(x)}$ олон гишүүнттэйгээр $[l,m)$ рүү доош шилжье.
  3. Энэ нь $A(x_l), \dots, A(x_{m-1})$-г рекурсивээр тооцоолно, одоо $A(x) \pmod{P_{m,r}(x)}$-тэйгээр $[m,r)$-д мөн адилыг хий.
  4. Эхний ба хоёр дахь рекурсив дуудалтын үр дүнг залгаж буцаа.

Бүх процедур $O(n \log^2 n)$-д ажиллана.

Интерполяц

$(x_i, y_i)$ хосуудын багц өгөгдсөн үед олон гишүүнтийг интерполяцлах Лагранжийн шууд томьёо байдаг:

$$\boxed{A(x) = \sum\limits_{i=1}^n y_i \prod\limits_{j \neq i}\dfrac{x-x_j}{x_i - x_j}}$$

Үүнийг шууд тооцоолох нь хэцүү зүйл боловч хуваа ба ялагтун аргаар $O(n \log^2 n)$-д тооцоолж болох нь тогтоогдсон:

$P(x) = (x-x_1)\dots(x-x_n)$ гэж авч үзье. $A(x)$ дахь хуваарийн коэффициентүүдийг мэдэхийн тулд бид дараах үржвэрүүдийг тооцоолох ёстой:

$$ P_i = \prod\limits_{j \neq i} (x_i-x_j) $$

Гэвч $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)$-ийн язгуур байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөлд энэ нь тэгтэй тэнцүү байна.

Тэгш хэмийн үүднээс бид үүнийг $b_m^n$-ээр мөн үржүүлж, бүх үржвэрийг дараах хэлбэрээр дахин бичиж болно:

$$\boxed{\mathcal{R}(A, B) = b_m^n\prod\limits_{j=0}^m A(\mu_j) = b_m^n a_m^n \prod\limits_{i=0}^n \prod\limits_{j=0}^m (\mu_j - \lambda_i)= (-1)^{mn}a_n^m \prod\limits_{i=0}^n B(\lambda_i)}$$

Дээр тодорхойлсон утгыг $A(x)$ ба $B(x)$ олон гишүүнтүүдийн резултант гэж нэрлэдэг. Тодорхойлолтоос та дараах шинж чанаруудыг олж болно:

  1. $\mathcal R(A, B) = (-1)^{nm} \mathcal R(B, A)$.
  2. $n=0$ эсвэл $m=0$ үед $\mathcal R(A, B)= a_n^m b_m^n$.
  3. Хэрэв $b_m=1$ бол дурын олон гишүүнт $C(x)$ ба $n,m \geq 1$-ийн хувьд $\mathcal R(A - CB, B) = \mathcal R(A, B)$.
  4. Эндээс дурын $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;
    }
}

Хагас-ХИЕХ алгоритм

ХИЕХ ба резултантыг $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 функц хэлбэрээр олж болно.

Хагас-ХИЕХ хэрэгжсэний дараа та $\gcd(a, b)$ ба $0$ хос болтол олон гишүүнтэд түүнийг давтан хэрэглэж болно.

Бодлогууд