來學(xué)習(xí)一個(gè)多項(xiàng)式全家桶。

基本算法

FFT

先咕著。

NTT

先咕著。

數(shù)學(xué)

多項(xiàng)式求導(dǎo)

這其實(shí)是高中數(shù)學(xué)內(nèi)容。

對于多項(xiàng)式 \(F(x)=u(x)+v(x)\)，它的導(dǎo)數(shù)\(F'(x)=u'(x)+v'(x)\)。

再結(jié)合\(u(x)=x^n, u'(x)=nx^{n-1}\)，就可以愉快地線性時(shí)間求出導(dǎo)數(shù)。

多項(xiàng)式積分

直接根據(jù)公式

那么右邊就是

原函數(shù)

\(c\)咋整啊，直接等 \(0\) 吧。

那么就可以線性做完了。

多項(xiàng)式求逆

對于函數(shù) \(F(x)\)，求一個(gè)多項(xiàng)式 \(G\)(x)，使得在每一項(xiàng)系數(shù)模 \(x^n\) 時(shí)，有\(F(x)*G(x) \equiv 1 \pmod {x^n}\)。

如果 \(F\) 只有一項(xiàng)，那么就變成了單項(xiàng)式求逆元。

如果有 \(n\) 項(xiàng)呢？

假設(shè)我們先求出來了模 \(x^{\lceil \frac{n}{2} \rceil}\) 的逆為 \(G'\)，則：

且

上減下，除掉 \(F\)

平方

拆開

乘上 \(F\)

移項(xiàng)

遞歸算就行了。

多項(xiàng)式對數(shù)函數(shù)

多項(xiàng)式 \(F\)，求 \(G \equiv ln(F) \pmod {x^n}\)。

設(shè) \(A(x)=ln(x)\)，有

求導(dǎo)

求導(dǎo)求逆乘一起就行了。

泰勒展開

求一個(gè)函數(shù) \(f(x)\) 在某一點(diǎn)的值，可以構(gòu)造一個(gè)函數(shù) \(g(x)\)，使得

其中 \(f^n(0)\) 表示對原函數(shù)的圖像上 \(0\) 這個(gè)點(diǎn)進(jìn)行 \(n\) 階求導(dǎo)。

牛頓迭代

求函數(shù) \(G(x)\) 的零點(diǎn)，即求滿足 \(G(F(z)) \equiv 0 \pmod {z^n}\) 的多項(xiàng)式 \(F(z)\)。

\(n=1\) 時(shí)，提前求出\(G(F(z)) \equiv 0 \pmod {z^n}\)。

現(xiàn)在假設(shè)求出了

進(jìn)行泰勒展開

因?yàn)?\(F(z)\) 和 \(F_0(z)\) 的最后 \(\lceil \frac{n}{2} \rceil\) 項(xiàng)相同，所以 \((F(z)-F_0(z))^2\) 的最低非 \(0\) 項(xiàng)次數(shù)大于 $2 \lceil \frac{n}{2} \rceil $，所以

且 \(G(F(z)) \equiv 0 \pmod{z^n}\)，得到

迭代就可以了。

多項(xiàng)式指數(shù)函數(shù)

求 \(F(x)\equiv e^{A(x)} \pmod{x^n}\)。

取對數(shù)并移項(xiàng)

設(shè) \(G(F(x)) = \ln F(x) - A(x)\)，則求 \(G(F(x))=0\)。

求導(dǎo)

假設(shè)已經(jīng)求出了 \(F_0(x) \equiv e^{A(x)} \pmod{x^{\lceil\frac{n}{2}\rceil}}\)，代入牛頓迭代公式

且 \(A(0)=0\)，所以 \(F(x)\) 的常數(shù)項(xiàng)為 \(1\)。

也可以遞歸求解了。