文章目錄
-
- 多項式求逆
- 多項式取模(多項式帶餘除法)
- 多項式開方
- 多項式求對數
- 多項式牛頓疊代
- 多項式exp
- 多項式的幂
多項式求逆
已知 f ( x ) f(x) f(x),要求出 g ( x ) g(x) g(x)滿足 f ( x ) g ( x ) ≡ 1 ( m o d x n ) f(x)g(x)\equiv 1\pmod {x^n} f(x)g(x)≡1(modxn)
其中模 x n x^n xn的意義是将指數大于等于 n n n的部分都去掉。
将 n n n向上擴充為 2 k − 1 2^k-1 2k−1。假設我們已求出 g ′ ( x ) g'(x) g′(x)滿足 f ( x ) g ′ ( x ) ≡ 1 ( m o d x n 2 ) f(x)g'(x)\equiv 1\pmod{x^\frac{n}{2}} f(x)g′(x)≡1(modx2n)
顯然在模 x n x^n xn成立的條件在模 x n 2 x^\frac{n}{2} x2n時也成立。于是上兩式相減得 f ( x ) ( g ( x ) − g ′ ( x ) ) ≡ 0 ( m o d x n 2 ) f(x)(g(x)-g'(x))\equiv 0\pmod{x^\frac{n}{2}} f(x)(g(x)−g′(x))≡0(modx2n)
由于 f ( x ) ̸ ≡ 0 f(x)\not\equiv0 f(x)̸≡0,是以 g ( x ) − g ′ ( x ) ≡ 0 ( m o d x n 2 ) g(x)-g'(x)\equiv 0\pmod{x^\frac{n}{2}} g(x)−g′(x)≡0(modx2n)
兩邊平方得 g 2 ( x ) − 2 g ( x ) g ′ ( x ) + g ′ 2 ( x ) ≡ 0 ( m o d x n ) g^2(x)-2g(x)g'(x)+g'^2(x)\equiv 0\pmod{x^n} g2(x)−2g(x)g′(x)+g′2(x)≡0(modxn)
兩邊同乘 f ( x ) f(x) f(x)得 g ( x ) − 2 g ′ ( x ) + f ( x ) g ′ 2 ( x ) ≡ 0 ( m o d x n ) g(x)-2g'(x)+f(x)g'^2(x)\equiv 0\pmod{x^n} g(x)−2g′(x)+f(x)g′2(x)≡0(modxn)
于是 g ( x ) ≡ 2 g ′ ( x ) − f ( x ) g ′ 2 ( x ) ( m o d x n ) g(x)\equiv 2g'(x)-f(x)g'^2(x)\pmod{x^n} g(x)≡2g′(x)−f(x)g′2(x)(modxn)
用FFT計算,遞歸求解即可。總時間複雜度為 O ( n log n ) O(n\log n) O(nlogn)。
口訣:減去平成(2019.2.7)
inline pol inv(pol g) {
int n = g.size(), m = n >> 1;
if(n == 1) return unipol(inv(g[0]));
pol f0 = g; f0.resize(m);
f0 = inv(f0);
f0.resize(n<<1); g.resize(n<<1);
ntt(f0, 1); ntt(g, 1);
for(int i = 0; i < n<<1; i++) g[i] = mul(f0[i], sub(2, mul(g[i], f0[i])));
ntt(g, 0); g.resize(n);
return g;
}
多項式取模(多項式帶餘除法)
給定 f ( x ) f(x) f(x)、 g ( x ) g(x) g(x),要求 q ( x ) q(x) q(x)、 r ( x ) r(x) r(x)滿足
f ( x ) = g ( x ) q ( x ) + r ( x ) f(x)=g(x)q(x)+r(x) f(x)=g(x)q(x)+r(x)
設 f ( x ) f(x) f(x)的階為 n − 1 n-1 n−1, g ( x ) g(x) g(x)的階為 m − 1 m-1 m−1,則 q ( x ) q(x) q(x)的階為 n − m n-m n−m, r ( x ) r(x) r(x)的階小于 m − 1 m-1 m−1。
将 f ( x ) f(x) f(x)、 r ( x ) r(x) r(x)的系數在 [ 0 , n − 1 ] [0,n-1] [0,n−1]内翻轉, g ( x ) g(x) g(x)的系數在 [ 0 , m − 1 ] [0,m-1] [0,m−1]内翻轉, q ( x ) q(x) q(x)的系數在 [ 0 , n − m ] [0,n-m] [0,n−m]内翻轉。以下标 r r r表示翻轉,則同樣有 f r ( x ) = g r ( x ) q r ( x ) + r r ( x ) f_r(x)=g_r(x)q_r(x)+r_r(x) fr(x)=gr(x)qr(x)+rr(x)
由于 r ( x ) r(x) r(x)的指數範圍是 [ 0 , m − 2 ] [0,m-2] [0,m−2],因而 r r ( x ) r_r(x) rr(x)的指數範圍是 [ n − m + 1 , n − 1 ] [n-m+1,n-1] [n−m+1,n−1]。是以
f r ( x ) ≡ g r ( x ) q r ( x ) ( m o d x n − m + 1 ) f_r(x)\equiv g_r(x)q_r(x)\pmod{x^{n-m+1}} fr(x)≡gr(x)qr(x)(modxn−m+1) q r ( x ) ≡ f r ( x ) g r ( x ) − 1 ( m o d x n − m + 1 ) q_r(x)\equiv f_r(x)g_r(x)^{-1}\pmod{x^{n-m+1}} qr(x)≡fr(x)gr(x)−1(modxn−m+1)
由于 q r ( x ) q_r(x) qr(x)的指數範圍是 [ 0 , n − m ] [0,n-m] [0,n−m],模 x n − m + 1 x^{n-m+1} xn−m+1對其不産生影響。于是可由此直接得到 q ( x ) q(x) q(x)。
inline pol dvd(pol a, pol b) {
int n = a.size(), m = b.size();
if(n < m) return unipol(0);
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
b.resize(ext(n-m+1));
b = inv(b);
a.resize(n-m+1);
a = a * b;
a.resize(n-m+1);
reverse(a.begin(), a.end());
return a;
}
多項式開方
求 g ( x ) g(x) g(x)滿足 g 2 ( x ) ≡ f ( x ) ( m o d x n ) g^2(x)\equiv f(x)\pmod{x^n} g2(x)≡f(x)(modxn)。
假設已求出 g ′ ( x ) g'(x) g′(x)滿足 g ′ 2 ( x ) ≡ f ( x ) ( m o d x n 2 ) g'^2(x)\equiv f(x)\pmod{x^\frac{n}{2}} g′2(x)≡f(x)(modx2n),則 g ′ 2 ( x ) − g 2 ( x ) ≡ 0 ( m o d x n 2 ) g'^2(x)-g^2(x)\equiv 0\pmod{x^\frac{n}{2}} g′2(x)−g2(x)≡0(modx2n) ( g ′ ( x ) + g ( x ) ) ( g ′ ( x ) − g ( x ) ) ≡ 0 ( m o d x n 2 ) (g'(x)+g(x))(g'(x)-g(x))\equiv 0\pmod{x^\frac{n}{2}} (g′(x)+g(x))(g′(x)−g(x))≡0(modx2n) g ′ ( x ) − g ( x ) ≡ 0 ( m o d x n 2 ) g'(x)-g(x)\equiv 0\pmod{x^\frac{n}{2}} g′(x)−g(x)≡0(modx2n)
兩邊平方得 g 2 ( x ) − 2 g ( x ) g ′ ( x ) + g ′ 2 ( x ) ≡ 0 ( m o d x n ) g^2(x)-2g(x)g'(x)+g'^2(x)\equiv 0\pmod{x^n} g2(x)−2g(x)g′(x)+g′2(x)≡0(modxn)
于是 g ( x ) ≡ f ( x ) + g ′ 2 ( x ) 2 g ′ ( x ) ( m o d x n ) g(x)\equiv\frac{f(x)+g'^2(x)}{2g'(x)}\pmod{x^n} g(x)≡2g′(x)f(x)+g′2(x)(modxn)
遞歸求解即可。注意如果取模,計算常數項時應用二次剩餘。
int inv2 = inv(2);
inline pol sqt(pol g) {
int n = g.size(), m = n >> 1;
if(n == 1) return unipol(msqrt(1));
pol g0 = g; g0.resize(m);
pol f0 = sqt(g0), invf0 = f0;
invf0.resize(n);
for(int i = 0; i < n; i++) invf0[i] = mul(invf0[i], 2);
invf0 = inv(invf0);
f0 = f0 * f0;
for(int i = 0; i < n; i++) Add(g[i], f0[i]);
g = g * invf0;
g.resize(n);
return g;
}
現在你已經可以做小朋友與二叉樹了。
11.19 here
多項式求對數
求 ln f ( x ) ( m o d x n ) \ln f(x)\pmod {x^n} lnf(x)(modxn)。
ln f ( x ) ≡ ∫ ( ln f ( x ) ) ′ ≡ ∫ f ( x ) ′ f ( x ) ( m o d x n ) \ln f(x)\equiv \int(\ln f(x))'\equiv \int\frac{f(x)'}{f(x)}\pmod{x^n} lnf(x)≡∫(lnf(x))′≡∫f(x)f(x)′(modxn)。用多項式求導、多項式積分和多項式求逆即可。
inline pol ln(pol g) {
int n = g.size();
pol gg; gg.resize(n);
for(int i = 0; i < n-1; i++) gg[i] = mul(i+1, g[i+1]);
gg[n-1] = 0;
pol f = inv(g); f.resize(n<<1); gg.resize(n<<1);
ntt(f, 1); ntt(gg, 1);
for(int i = 0; i < n<<1; i++) gg[i] = mul(gg[i], f[i]);
ntt(gg, 0);
for(int i = 1; i < n; i++) g[i] = mul(inv(i), gg[i-1]);
g[0] = 0;
return g;
}
多項式牛頓疊代
給定 g ( f ( x ) ) g(f(x)) g(f(x)),求其零點(即求一個 f ( x ) f(x) f(x)使 g ( f ( x ) ) ≡ 0 ( m o d x n ) g(f(x))\equiv 0\pmod {x^n} g(f(x))≡0(modxn))。
多項式上的牛頓疊代公式 設 f 0 ( x ) ≡ f ( x )   m o d   x n 2 ( m o d x n ) f_0(x)\equiv f(x)\bmod x^\frac{n}{2}\pmod{x^n} f0(x)≡f(x)modx2n(modxn),則有 f ( x ) ≡ f 0 ( x ) − g ( f 0 ( x ) ) g ′ ( f 0 ( x ) ) ( m o d x n ) f(x)\equiv f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}\pmod{x^n} f(x)≡f0(x)−g′(f0(x))g(f0(x))(modxn)
遞歸解決即可。注意每次問題規模減半,每層複雜度 O ( n log n ) O(n\log n) O(nlogn),是以總複雜度為 O ( n log n ) O(n\log n) O(nlogn)。
多項式exp
求 f ( x ) ≡ e h ( x ) ( m o d x n ) f(x)\equiv e^{h(x)}\pmod {x^n} f(x)≡eh(x)(modxn)。
兩邊取對數得 ln f ( x ) ≡ h ( x ) ( m o d x n ) \ln f(x)\equiv h(x)\pmod{x^n} lnf(x)≡h(x)(modxn)
設 g ( f ( x ) ) ≡ ln f ( x ) − h ( x ) ( m o d x n ) g(f(x))\equiv \ln f(x)-h(x)\pmod{x^n} g(f(x))≡lnf(x)−h(x)(modxn),則問題變為求該函數的零點。由多項式上的牛頓疊代公式,有 f ( x ) ≡ f 0 ( x ) − ln f 0 ( x ) − h ( x ) 1 f 0 ( x ) ( m o d x n ) f(x)\equiv f_0(x)-\frac{\ln f_0(x)-h(x)}{\frac{1}{f_0(x)}}\pmod{x^n} f(x)≡f0(x)−f0(x)1lnf0(x)−h(x)(modxn) f ( x ) ≡ f 0 ( x ) ⋅ ( 1 − ln f 0 ( x ) + h ( x ) ) ( m o d x n ) f(x)\equiv f_0(x)\cdot(1-\ln f_0(x)+h(x))\pmod{x^n} f(x)≡f0(x)⋅(1−lnf0(x)+h(x))(modxn)
用牛頓疊代的方法遞歸即可。
inline pol exp(pol g) {
int n = g.size(), m = n >> 1;
if(n == 1) return unipol(1);
pol f0 = g; f0.resize(m);
f0 = exp(f0); f0.resize(n);
pol lnf0 = ln(f0);
f0.resize(n<<1); lnf0.resize(n<<1); g.resize(n<<1);
Add(g[0], 1);
ntt(f0, 1); ntt(lnf0, 1); ntt(g, 1);
for(int i = 0; i < n<<1; i++) g[i] = mul(f0[i], sub(g[i], lnf0[i]));
ntt(g, 0);
g.resize(n);
return g;
}
多項式的幂
求 f g ( x ) ( x ) f^{g(x)}(x) fg(x)(x)。
≡ e f ( x ) ln g ( x ) ( m o d x n ) \equiv e^{f(x)\ln g(x)}\pmod{x^n} ≡ef(x)lng(x)(modxn)
用多項式求對數和多項式exp即可。
Talk is cheap, show me the code!
[+] view code
FFT、NTT及FWT見多項式基礎I。
多項式多點求值和多項式快速插值見多項式基礎III。
另有任意模數NTT,無迹可循。