多項(xiàng)式相關(guān)操作學(xué)習(xí)筆記

標(biāo)簽： 多項(xiàng)式

---

說(shuō)在前邊

記錄一下相關(guān)的多項(xiàng)式操作，順便存?zhèn)€模板。（多點(diǎn)求值之后的部分，有點(diǎn)寫不動(dòng)了。。。留坑留坑

---

多項(xiàng)式

---

定義

給定一個(gè)環(huán)\(R\)(\(R\)通常是交換環(huán)，可以是有理數(shù)、實(shí)數(shù)或者復(fù)數(shù)等等)以及一個(gè)未知數(shù)\(X\)，則任何形同：\[a_0 + a_1X + ... +a_{n-1}X^{n-1} + a_nX^n\]的代數(shù)表達(dá)式叫做\(R\)上的一元多項(xiàng)式。其中\(a_0,a_1,... ,a_n\)是\(R\)中的元素。未知數(shù)不代表任何值，但環(huán) \(R\)上的所有運(yùn)算都對(duì)它適用。在不至于混淆的情形下，一般將一元多項(xiàng)式簡(jiǎn)稱為多項(xiàng)式。可以證明，兩個(gè)多項(xiàng)式的和、差與積仍然是多項(xiàng)式，即多項(xiàng)式組成一個(gè)環(huán) \(R[X]\)，稱為\(R\)上的（一元）多項(xiàng)式環(huán)。—— From Wiki

---

多項(xiàng)式乘法

計(jì)算兩個(gè)多項(xiàng)式相乘時(shí)，首先使用乘法對(duì)加法的分配律將各項(xiàng)拆出，然后運(yùn)用乘法結(jié)合律整合每一項(xiàng)，最后和加法一樣整合同類項(xiàng)，就能得到乘積多項(xiàng)式，形式化的說(shuō)：
\[ P = a_0 + a_1X + ... +a_{n-1}X^{n-1} + a_nX^n \\ Q = b_0 + b_1X + ... +b_{n-1}X^{n-1} + b_nX^m \\ PQ = \sum_{i+j=0}a_ib_j +\sum_{i+j=1}a_ib_jX + ... + \sum_{i+j=n+m}a_ib_jX^{n+m} \]

---

離散傅里葉變換（DFT）

定義

對(duì)于\(N\)點(diǎn)序列\(x[n]\)，它的\(DFT\)為:
\[ X[k] = \sum_{n = 0}^{N-1}e^{-i\frac{2\pi}{N}nk}x[n] ~~k = 0,1,...,N-1\]
離散傅里葉變換的逆變換（IDFT）為:
\[ x[n] = \frac{1}{N}\sum_{k = 0}^{N-1}e^{i\frac{2\pi}{N}nk}X[k]~~n = 0,1,...,N-1 \]

---

DFT與圓周卷積

圓周移位
若\(f(n) = x((n+m))_NR_N(n)\)，成\(f(n)\)為\(x(n)\)的\(m\)點(diǎn)圓周移位序列。
步驟：1）將x(n)以N為周期進(jìn)行周期延拓；2）移位m點(diǎn)；3）取主值序列

若\(x(n), y(n)\)進(jìn)行DFT，\(x(n) \leftrightarrow X(k), y(n) \leftrightarrow Y(k)\) 則
\[ F(k) = X(k)Y(k) \leftrightarrow f(n) = \sum_{m=0}^{N-1}x(m)y((n-m))_NR_N(n) \]

---

有限長(zhǎng)序列的圓周卷積與線性卷積

\(x(n)\):\(M\)點(diǎn)序列，\(y(n)\):\(N\)點(diǎn)序列

線性卷積：\[x(n)*y(n) = \sum_{m=-\infty}^{\infty} x(m)y(n-m)\]

可知\(f(n)\)的非\(0\)區(qū)間為\([0,M+N-2]\)

圓周卷積是線性卷積以\(L\)為周期延拓后，取\([0,L-1]\)間的主值序列。
當(dāng) \(L \geq N+M-1\) 時(shí)，圓周卷積等價(jià)于線性卷積

---

DSP角度的解釋

從DTFT到DFS，從DFS到DFT，從DFT到FFT，從一維到二維

---

一些變換

快速傅里葉變換（FFT）

很久之前參考算導(dǎo)寫的FFT學(xué)習(xí)筆記

---

快速哈特萊變換（FHT）

FHT是一種實(shí)序列變換

---

快速數(shù)論變換（NTT）

NTT是在整數(shù)域進(jìn)行的，FFT中通過(guò)n次單位福根運(yùn)算，即滿足\(W^n = 1\)的\(W\)，而NTT，將\(g^{\frac{P-1}{N}}(mod~P)\) 看作與 \(e^{-\frac{2\pi i}{N}}\) 等價(jià)，這里\(g\)是模素?cái)?shù)\(P\)的原根。綜上，數(shù)論變換的公式如下：
\[ X_k ≡ \sum_{n=0}^{N-1}x_ng^{nk}(mod~P)~~~ k = 0, 1, ...,N-1 \]
逆變換為：
\[ x_n ≡ \frac{1}{N}\sum_{k=0}^{N-1}X_kg^{-nk}(mod~P)~~~ n = 0, 1, ...,N-1 \]

Code

#include <cstdio> #include <algorithm> typedef long long ll; constexpr int N = 1 << 18 | 5; constexpr int Mod = 998244353; constexpr int G = 3; ll qpow(ll a, ll b) {ll ans = 1;for(; b; a = (a * a) % Mod, b >>= 1)if(b & 1) ans = (ans * a) % Mod;return ans; } int siz, rev[N]; ll w[N]; inline void init(int n) {for(siz = 1; siz < n; siz <<= 1);for(int i = 0; i < siz; ++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (siz >> 1));ll pr = qpow(G, (Mod-1) / siz);w[siz / 2] = 1;for(int i = 1; i < siz / 2; ++i) w[siz/2+i] = (w[siz/2+i-1]*pr) % Mod;for(int i = siz / 2 - 1; i >= 0; --i) w[i] = w[i << 1]; } inline void DFT(ll A[], int L) {static ll t[N];int shift = __builtin_ctz(siz) - __builtin_ctz(L);for(int i = 0; i != L; ++i) t[rev[i] >> shift] = A[i];for(int d = 1; d != L; d <<= 1)for(int i = 0; i != L; i += d << 1)for(int j = 0; j != d; ++j) {ll tmp = t[i + d + j] * w[d + j] % Mod;t[i + d + j] = t[i + j] - tmp;t[i + j] = t[i + j] + tmp;if(t[i + d + j] < 0) t[i + d + j] += Mod;if(t[i + j] >= Mod) t[i + j] -= Mod;}for(int i = 0; i != L; ++i) A[i] = t[i] % Mod; } inline void IDFT(ll A[], int L) {std::reverse(A + 1, A + L);DFT(A, L);ll Inv_L = qpow(L, Mod - 2);for(int i = 0; i != L; ++i) (A[i] *= Inv_L) %= Mod; } int n, m, L; ll a[N], b[N]; int main() {scanf("%d%d",&n,&m);for(int i = 0; i <= n; ++i) scanf("%lld", &a[i]);for(int i = 0; i <= m; ++i) scanf("%lld", &b[i]);for(L = 1; L <= m+n; L <<= 1); init(L);DFT(a, L); DFT(b, L);for(int i = 0; i <= L; ++i) a[i] = a[i] * b[i] % Mod;IDFT(a, L);for(int i = 0; i <= n+m; ++i) printf("%lld ",a[i]); puts("");return 0; }

---

任意模數(shù)FFT

題意：給兩個(gè)多項(xiàng)式\(f(x)\) 和 \(g(x)\)以及一個(gè)模數(shù)\(p(p \leq 10^9)\), 求\(f * g (mod ~ p)\)

做法：任意模數(shù)NTT，最大的數(shù)為\(p^2 max(n,m) \leq 10^{23}\), 所以一般選三個(gè)模數(shù)即可，求出這三個(gè)模數(shù)下的答案，然后中國(guó)剩余定理。

設(shè)當(dāng)前這一項(xiàng)的系數(shù)為\(x\)，三個(gè)模數(shù)分別為\(A, B, C\), 那么：
\[ x ≡ x_1 (mod ~ A) \\ x ≡ x_2 (mod ~ B) \\ x ≡ x_3 (mod ~ C) \]
先合并前兩項(xiàng)：
\[ x_1 + k_1A = x_2 + k_2B = x \\ x_1 + k_1A ≡ x_2 ~(mod ~ B) \\ k_1 ≡ ~\frac {x_2 - x_1} {A}~(mod ~B) \]
及求出\(x ≡ x_1 + k_1A ~(mod ~AB)\)， 記作\(x_4 = x_1 + k_1A\)，
\[ x_4 + k_4AB = x_3 + k_3C \\ x_4 + k_4AB ≡ x_3 ~(mod ~C) \\ k_4 ≡ \frac{x3 - x4}{AB} ~(mod ~C) \]
n那么\(x ≡ x_4 + k_4AB ~(mod~ABC)\)，因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(x < ABC\), 所以\(x = x_4 + k_4AB\)

Code[洛谷P4245]

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; constexpr int N = 1 << 18 | 5; constexpr ll Mod1 = 469762049; constexpr ll Mod2 = 998244353; constexpr ll Mod3 = 1004535809; constexpr ll M = Mod1 * Mod2; constexpr int G = 3; using namespace std; inline ll Mul(ll a, ll b, ll Mod) {ll ans = 0; ((a %= Mod) += Mod)%= Mod;for(; b; a = (a + a) % Mod, b >>= 1)if(b & 1) ans = (ans + a) % Mod;return ans; } inline ll qpow(ll a, ll b, ll Mod) {ll ans = 1; ((a %= Mod) += Mod)%= Mod;for(; b; a = (a * a) % Mod, b >>= 1)if(b & 1) ans = (ans * a) % Mod;return ans; } int siz, rev[N]; ll w[4][N]; inline void init_w(int typ, ll Mod) {ll pr = qpow(G, (Mod-1) / siz, Mod);w[typ][siz / 2] = 1;for(int i = 1; i < siz / 2; ++i) w[typ][siz/2+i] = (w[typ][siz/2+i-1]*pr) % Mod;for(int i = siz / 2 - 1; i >= 0; --i) w[typ][i] = w[typ][i << 1]; } inline void init(int n) {for(siz = 1; siz < n; siz <<= 1);for(int i = 0; i < siz; ++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (siz >> 1));init_w(1,Mod1); init_w(2,Mod2); init_w(3,Mod3); } inline void DFT(ll A[], int L, int typ, ll Mod) {static ll t[N];int shift = __builtin_ctz(siz) - __builtin_ctz(L);for(int i = 0; i != L; ++i) t[rev[i] >> shift] = A[i];for(int d = 1; d != L; d <<= 1)for(int i = 0; i != L; i += d << 1)for(int j = 0; j != d; ++j) {ll tmp = t[i + d + j] * w[typ][d + j] % Mod;t[i + d + j] = t[i + j] - tmp;t[i + j] = t[i + j] + tmp;if(t[i + d + j] < 0) t[i + d + j] += Mod;if(t[i + j] >= Mod) t[i + j] -= Mod;}for(int i = 0; i != L; ++i) A[i] = t[i] % Mod; } inline void IDFT(ll A[], int L, int typ, ll Mod) {std::reverse(A + 1, A + L);DFT(A, L, typ, Mod);ll Inv_L = qpow(L, Mod - 2, Mod);for(int i = 0; i != L; ++i) (A[i] *= Inv_L) %= Mod; }int n, m, L, P; ll a[N], b[N], c[N], d[N], ans[3][N];ll CRT(ll a1, ll a2, ll a3) {ll k1 = Mul((a2 - a1),qpow(Mod1, Mod2-2, Mod2), Mod2);ll a4 = a1 + k1*Mod1;ll k4 = Mul((a3 - a4) , qpow(M, Mod3-2, Mod3), Mod3);return (a4%P + Mul(k4 , M, P)) % P; }int main() {scanf("%d%d%d",&n,&m,&P);for(int i = 0; i <= n; ++i) scanf("%lld", &a[i]);for(int i = 0; i <= m; ++i) scanf("%lld", &b[i]);for(L = 1; L <= m+n; L <<= 1); init(L);memcpy(c, a, sizeof(a)); memcpy(d, b, sizeof(a)); DFT(c, L, 1, Mod1); DFT(d, L, 1, Mod1);for(int i = 0; i <= L; ++i) ans[0][i] = c[i] * d[i] % Mod1; memcpy(c, a, sizeof(a)); memcpy(d, b, sizeof(a)); DFT(c, L, 2, Mod2); DFT(d, L, 2, Mod2);for(int i = 0; i <= L; ++i) ans[1][i] = c[i] * d[i] % Mod2;memcpy(c, a, sizeof(a)); memcpy(d, b, sizeof(a)); DFT(c, L, 3, Mod3); DFT(d, L, 3, Mod3);for(int i = 0; i <= L; ++i) ans[2][i] = c[i] * d[i] % Mod3;IDFT(ans[0], L, 1, Mod1); IDFT(ans[1], L, 2, Mod2); IDFT(ans[2], L, 3, Mod3);for(int i = 0; i <= n+m; ++i) {printf("%lld ",CRT(ans[0][i], ans[1][i], ans[2][i]));}puts("");return 0; }

---

多項(xiàng)式的各種操作

多項(xiàng)式逆元

題意：給定多項(xiàng)式\(A(x)\)，請(qǐng)求出一個(gè)多項(xiàng)式\(B(x)\)，滿足\(A(x)*B(x) ≡ 1 (mod~x^n)\)

做法：

當(dāng)\(n = 1\)時(shí),\(A(x) ≡ c (mod~x)\)，這樣\(A^{-1}(x) ≡ c^{-1}(mod~x)\)

\(n > 1\)時(shí)，設(shè)\(B(x) ≡ A^{-1}(x)(mod~x)\)，則有\[A(x)B(x) ≡ 1 (mod~x^n)\]
假設(shè)在 \(mod~x^{\lceil \frac{n}{2} \rceil}\)意義下，\(A(x)\)的逆元是\(B(x)\)并且我們已經(jīng)求出，那么有\[A(x)B'(x) ≡ 1 （mod~x^{\lceil \frac{n}{2} \rceil})\]
顯然\[A(x)B(x) ≡ 1 （ mod~x^{\lceil \frac{n}{2} \rceil})\]
相減可得\[B(x)-B'(x) ≡ 0 (mod~x^{\lceil \frac{n}{2} \rceil})\]
兩邊平方得\[B^2(x) - 2B'(x)B(x) + B'^2(x) ≡ 0 (mod~x^n)\]
兩邊同乘\(A(x)\)，移項(xiàng)可得\[B(x) ≡ 2B'(x) - A(x)B'^2(x) (mod ~x^n)\]

再利用\(FFT\)加速運(yùn)算即可。

Code[洛谷P4238]

int n, L; ll a[N], b[N], tmp[N]; void PloyInv(ll A[], ll B[], int n) {if(n == 1) {B[0] = qpow(A[0], Mod - 2, Mod); return;}PloyInv(A, B, (n + 1) >> 1);int p = 1; while(p < n<<1) p <<= 1;copy(A, A+n, tmp); fill(tmp+n, tmp+p, 0);DFT(tmp, p); DFT(B, p);for(int i = 0; i != p; ++i) {B[i] = (2 - tmp[i] * B[i] % Mod) * B[i] % Mod;if(B[i] < 0) B[i] += Mod;}IDFT(B, p);fill(B + n, B + p, 0); } int main() {scanf("%d",&n);for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);for(L = 2; L <= 2*n-2; L <<= 1); init(L);PloyInv(a, b, n);for(int i = 0; i < n; ++i) printf("%lld ",b[i]); puts("");return 0; }

---

多項(xiàng)式除法

題意：給定一\(n\)次多項(xiàng)式\(A(x)\)和一個(gè)\(m(m \leq n)\)次多項(xiàng)式\(B(x)\)，要求求出\(D(x), R(x)\)滿足\[A(x) = D(x)B(x) + R(x)\]且\(degD \leq degA - degB = n-m, ~degR < m\)

做法：首先，想辦法消除\(R(x)\)的影響。首先我定義一個(gè)運(yùn)算
\[A^R(x)= x^n A( \frac{1}{x} )\]
可以發(fā)現(xiàn)，這個(gè)操作在進(jìn)行系數(shù)反轉(zhuǎn)。

現(xiàn)在將原式的 \(x\) 全部替換為 \(\frac{1}{x}\) ，然后兩邊同乘\(x^n\)，可得
\[ x^nA(\frac{1}{x}) = x^{n-m}D(\frac{1}{x})x^mB(\frac{1}{x}) + x^{n-m+1}x^{m-1}R(\frac{1}{x}) \\ A^R(x) = D^R(x)B^R(x) + x^{n-m+1}R^R(x) \]

觀察這個(gè)式子，\(D(x)\)反轉(zhuǎn)后，次數(shù)不會(huì)高于\(n-m\)，而\(x^{n-m+1}R^R(x)\)這個(gè)部分最低次高于\(n-m\)，把上式放到\(mod ~x^{n-m+1}\)意義下，\(R(x)\)就會(huì)被消除，現(xiàn)在式子變?yōu)?span id="ze8trgl8bvbq" class="math display">\[A^R(x) ≡ D^{R}(x)B^R(x) (mod ~x^{n-m+1})\]這樣只需要求\(B^R(x)\)的逆元即可，\(D(x)\)可以通過(guò)回帶\(R(x)\)求得。

void PloyDiv(ll A[], ll B[], ll D[], ll R[], int n, int m) {static ll A0[N], B0[N];int p = 1, t = n - m + 1;while(p < t<<1) p <<= 1;fill(A0, A0 + p, 0);reverse_copy(B, B+m, A0);PloyInv(A0, B0, t);fill(B0+t, B0+p, 0);DFT(B0, p);reverse_copy(A, A+n, A0);fill(A0 + t, A0 + p, 0);DFT(A0, p);for(int i = 0; i != p; ++i)A0[i] = Mul(A0[i] , B0[i]);IDFT(A0, p);reverse(A0, A0+t); copy(A0, A0+t,D);p = 1; while(p < n) p <<= 1;fill(A0 + t, A0 + p, 0);DFT(A0, p);copy(B, B+m, B0);fill(B0 + m, B0 + p, 0);DFT(B0, p);for(int i = 0; i != p; ++i) A0[i] = Mul(A0[i] , B0[i]);IDFT(A0, p);for(int i = 0; i != m; ++i) R[i] = Dec(A[i] , A0[i]);fill(R+m, R+p, 0); }int main() {scanf("%d%d",&n,&m); ++n; ++m;for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);for(int i = 0; i < m; ++i) scanf("%lld", &b[i]);int LL = max(max(n, m), (n - m + 1) << 1);L = 1; while(L < LL) L <<= 1; init(L);PloyDiv(a, b, D, R, n, m);for(int i = 0; i < n-m+1; ++i) printf("%lld ",D[i]); puts("");for(int i = 0; i < m-1; ++i) printf("%lld ",R[i]); puts("");return 0; }

---

多項(xiàng)式牛頓迭代

題意：已知函數(shù)\(G(z)\)，求一個(gè)多項(xiàng)式 \(F(z) ~mod ~z^n\) ,滿足\[G(F(z)) ≡ 0 ~(mod ~z^n)\]

做法：類似多項(xiàng)式求逆的做法。
當(dāng)n = 1時(shí)，\(G(F(z)) ≡ 0 (mod~ z)\)要單獨(dú)求出。現(xiàn)在假設(shè)已經(jīng)求出\[G(F_0(z)) ≡ 0~(mod~z^{\lceil \frac{n}{2} \rceil})\]考慮如何將答案，擴(kuò)展至 \(mod~z^n\)下，把\(G(F(z))\)在\(F_0(z)\)泰勒展開(kāi)\[G(F(z))=G(F_0(z))+\frac{G'(F_0(z))}{1!}(F(z)-F_0(z)) + \frac{G''(F_0(z))}{2!}(F(z)-F_0(z))^2 + ...\]因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(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))≡G(F_0(z))+\frac{G'(F_0(z))}{1!}(F(z)-F_0(z)) ~(mod~z^n)\]因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(G(F(z)) ≡ 0 (mod z^n)\), 那么有\[F(z) ≡F_0(z) - \frac{G(F_0(z))}{G'(F_0(z))} ~(mod ~z^n)\]

---

多項(xiàng)式開(kāi)方

題意：給定一個(gè) \(n-1\) 次多項(xiàng)式 \(A(x)\)，求一個(gè)在 \(mod~x^n\) 意義下的多項(xiàng)式 \(B(x)\)，滿足\(B^2(x) ≡ A(x)~(mod~x^n)\)

做法：移向可得\(B^2(x) - A(x) ≡ 0 ~(mod~x^n)\) ，設(shè) \(G(B(x)) = B^2(x) - A(x)\), 有\(G'(B(x)) = 2B(x)\)，帶入牛頓迭代的式子里，則有：
\[ B(x) ≡ B_0(x) - \frac{B_0^2(x)-A(x)}{2B_0(x)} ≡ \frac{B_0^2(x)+A(x)}{2B_0(x)}~(mod~x^n) \]
注意到當(dāng) \(n = 1\) 時(shí)，如果題目不保證 \(a_0 = 1\)，可能需要計(jì)算二次剩余

Code[洛谷P5205]

void PloySqrt(ll A[], ll B[], int n) {static ll T[N];if(n == 1) {B[0] = 1; return;}int p = 1, hf = (n+1) >> 1; while(p < n<<1) p <<= 1;PloySqrt(A, B, hf); fill(B + hf, B + p, 0);PloyInv(B, T, n); fill(T + n, T + p, 0);DFT(T, p);fill(B + hf, B + p, 0);DFT(B, p >> 1);for(int i = 0; i != (p >> 1); ++i)B[i] = (B[i]*B[i]) % Mod;IDFT(B, p >> 1);for(int i = 0; i != n; ++i)B[i] = (A[i] + B[i]) % Mod * Inv2 % Mod;DFT(B, p);for(int i = 0; i != p; ++i)B[i] = (B[i] * T[i]) % Mod;IDFT(B, p); } int main() {scanf("%d",&n);for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);for(L = 2; L <= n << 1; L <<= 1); init(L);Inv2 = qpow(2,Mod-2,Mod);PloySqrt(a, b, n);for(int i = 0; i < n; ++i) printf("%lld ",b[i]); puts("");return 0; }

---

多項(xiàng)式 ln 和多項(xiàng)式 exp

---

多項(xiàng)式ln

• 定義：對(duì)于多項(xiàng)式 \(A(x) = \sum_{i \geq 1}a_ix^i\) 多項(xiàng)式ln有\[ln(1-A(x)) = -\sum_{i \geq 1}\frac{A^i(x)}{i}\]

• 計(jì)算
  現(xiàn)在有\(A(x) = 1 + \sum_{i \geq 1} a_ix^i\)
  對(duì) \(ln(A(x))\) 求導(dǎo)有\[(lnA(x))' = \frac{A'(x)}{A(x)}\] 只需計(jì)算 \(A(x)\) 的逆元，再完成求導(dǎo)和積分運(yùn)算即可

Code[洛谷4725]

void PloyD(ll A[],ll B[], int n) {copy(A, A+n, B);for(int i = 0; i < n-1; ++i) {B[i] = 1ll*B[i+1]*(i+1) % Mod;} B[n-1] = 0; } void PloyF(ll A[], ll B[], int n) {copy(A, A+n, B);for(int i = n-1; i; --i) {B[i] = B[i-1] * Inv[i] % Mod;} B[0] = 0; } void PloyLn(ll A[], ll B[], int n) {static ll T[N];int p = 1; while(p < n << 1) p <<= 1;PloyInv(A, T, n); fill(T+n, T+p, 0); DFT(T, p);PloyD(A,B,n); fill(B+n, B+p, 0); DFT(B, p);for(int i = 0; i != p; ++i) T[i] = (B[i] * T[i]) % Mod;IDFT(T, p);PloyF(T, B, n); fill(B+n, B+p, 0); } int main() {scanf("%d",&n);for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);for(L = 2; L <= n << 1; L <<= 1); init(L);Inv[1] = 1;for(ll i = 2; i <= L; i++)Inv[i] = (Mod - Mod / i) % Mod * Inv[Mod % i] % Mod;PloyLn(a, b, n);for(int i = 0; i < n; ++i) printf("%lld ",b[i]); puts("");return 0; }

---

多項(xiàng)式exp

• 定義：對(duì)于多項(xiàng)式 \(A(x) = \sum_{i \geq 1}a_ix^i\) 多項(xiàng)式exp有\[e^{A(x)} = \sum_{i \geq 0}\frac{A^i(x)}{i!}\]

• 計(jì)算

設(shè) \(F(x) = e^{A(x)}\) ，變形后得到 \[ln ~F(x) - A(x) = 0\] 構(gòu)造函數(shù) \[G(F(x)) = ln~F(x) - A(x) \], \(G'(F(x)) = \frac{1}{F(x)}\)，代入牛頓迭代\[F(x) ≡ F_0(x)(1 - ln~F_0(x) + A(x)) ~(mod~x^n)\] 當(dāng) \(n = 1\) 時(shí) \(F(x) = 1\)

Code[洛谷P4726]

void Ployexp(ll A[], ll B[], int n) {static ll T[N];if(n == 1) {B[0] = 1; return;}int p = 1, hf = (n + 1) >> 1; while(p < n<<1) p <<= 1;Ployexp(A, B, hf); fill(B + hf, B + p, 0);PloyLn(B, T, n);for(int i = 0; i != n; ++i) T[i] = (A[i] - T[i] + Mod) % Mod;++ T[0]; if(T[0] >= Mod) T[0] -= Mod;DFT(T, p); DFT(B, p);for(int i = 0; i != p; ++i) B[i] = B[i] * T[i] % Mod;IDFT(B, p); } int main() {scanf("%d",&n);for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);for(L = 2; L <= n << 1; L <<= 1); init(L);Inv[1] = 1;for(ll i = 2; i <= L; i++)Inv[i] = (Mod - Mod / i) % Mod * Inv[Mod % i] % Mod;Ployexp(a, b, n);for(int i = 0; i < n; ++i) printf("%lld ",b[i]); puts("");return 0; }

---

多項(xiàng)式任意次冪

題意：給出多項(xiàng)式\(A(x)\)，求\(A^k(x)，k \in Q\)

做法：

k為整數(shù)時(shí)可以快速冪

可以利用\(A^k(x) = e^{k~ln~A(x)}\) 計(jì)算

---

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

題意：給出多項(xiàng)式\(A(x)\)，求\(sin A(x)~(mod~x^n)\), \(cos A(x)~(mod~x^n)\)

做法：利用歐拉公式：\[e^{iA(x)} = cosA(x) + i sinA(x)\]與常規(guī)的多項(xiàng)式exp基本一致，只能用FFT，運(yùn)算全部為復(fù)數(shù)，注意邊界

---

多項(xiàng)式多點(diǎn)求值

---

多項(xiàng)式快速插值

---

多項(xiàng)式復(fù)合逆

---

多項(xiàng)式相關(guān)題目及應(yīng)用

分治FFT

題意：給定長(zhǎng)度為\(n-1\)的序列\(g[1],...,g[n-1]\)計(jì)算\(f[0],...,f[n-1]\)
\[ f[i] = \sum_{j=1}^i f[i-j]g[j] = \sum_{j=0}^{i-1} f[j]g[i-j] \]
有\(f[0] = 1\)

做法：CDQ+FFT。考慮已經(jīng)求出\([l,mid]\)的\(f[i]\)，計(jì)算他們堆\([mid+1,r]\)的貢獻(xiàn)$w[x], x \in [mid+1,r] $ 有
\[ w[x] = \sum_{i=l}^{mid} f[i]g[x-i] \rightarrow w[x] = \sum_{i=l}^{x-1} f[i]g[x-i] \]
（設(shè)\([mid+1,r]\)的\(f[i]=0\)）
令\(k = i-l\),
\[ w[x] = \sum_{k=0}^{x-l-1} f[k+l]g[x-k-l] = \sum_{k=0}^{x-l-1} a[k]b[x-l-1-k] \\ \]
我們湊出對(duì)應(yīng)的\(a[i], b[i]\)
\[ a[k] = f[k+l]\\ b[x-l-1-k] = g[x-l-k] \rightarrow \\ b[x-l-1+k] = g[x-l+k] \rightarrow \\ b[k-1] = g[k] \rightarrow b[k] = g[k+1] \]

Code[洛谷P4721 分治FFT]

int n, L; ll Ans[N], g[N], a[N], b[N]; void solve(int l, int r) {if(l == r) return;int mid = (l + r) >> 1;solve(l,mid);int len = r - l + 1, p = 1;for(;p < len; p <<= 1); // 我們最多需要r-l+1前項(xiàng)!!!for(int i = 0; i < p; ++ i) a[i] = b[i] = 0;for(int i = l; i <= mid; ++ i) a[i-l] = Ans[i];for(int i = 0; i <= r-l; ++ i) b[i] = g[i+1];DFT(a,p), DFT(b,p);for(int i = 0; i < p; ++i) a[i] = a[i]*b[i]%Mod;IDFT(a,p);rep(i,mid+1,r) {Ans[i] += a[i-l-1]; if(Ans[i] >= Mod) Ans[i] -= Mod;}solve(mid+1,r); } int main() {read(n); rep(i,1,n-1) read(g[i]);for(L = 2; L <= n << 1; L <<= 1); init(L);Ans[0] = 1;solve(0,n-1);rep(i,0,n-1) write(Ans[i]), putchar(' '); putchar('\n'); }

參考資料

DFT與圓周卷積

任意模數(shù)FFT

從DTFT到DFS，從DFS到DFT，從DFT到FFT，從一維到二維

一位神犇的Blog

另一位神犇的Blog

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/10342867.html

總結(jié)

以上是生活随笔為你收集整理的多项式相关操作学习笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。