多項(xiàng)式入門教程
\(\newcommand{\rd}{{\rm d}}\)原文鏈接 http://www.rzrgm.cn/zhouzhendong/p/polynomial.html
UPD(2020-08-27): 做了大量更新
多項(xiàng)式基礎(chǔ)操作
目錄
- 多項(xiàng)式求逆
- 牛頓迭代
- 二次剩余
- 多項(xiàng)式開(kāi)根
- 多項(xiàng)式對(duì)數(shù)函數(shù)
- 多項(xiàng)式指數(shù)函數(shù)
- 多項(xiàng)式快速冪
- 多項(xiàng)式除法、取模
- 多點(diǎn)求值與快速插值
前置技能
- 快速傅里葉變換(FFT) 和 快速數(shù)論變換(NTT)
http://www.rzrgm.cn/zhouzhendong/p/Fast-Fourier-Transform.html
關(guān)于代碼
下面這個(gè)鏈接是博主給出的示例代碼。如果在各個(gè)部分的示例代碼中有未定義的變量名或者函數(shù)名，請(qǐng)到代碼里找。
https://loj.ac/submission/872547
為了方便，這里也給出的一些重要的變量名/函數(shù)名的含義
mod = 998244353;
Pow,Add,Del等自行感受;
Fac[i] = i!;
Inv[i] = 1 / Fac[i];
Iv[i] = 1 / i;
typedef vector <int> vi;//代碼用來(lái)表示多項(xiàng)式類型
vi fix(vi a,int n);//將a的size調(diào)整為n（給a末尾補(bǔ)0或者刪除末尾直至a的size為n）
vi operator + (vi a,vi b);//多項(xiàng)式加法
vi operator - (vi a,vi b);//多項(xiàng)式減法
vi operator * (vi a,int b);//a*b
vi operator * (vi a,vi b);//a*b
vi polyinv(vi a);//多項(xiàng)式求逆
vi Der(vi a);//多項(xiàng)式求導(dǎo)
vi Int(vi a);//多項(xiàng)式積分
vi polyln(vi a);//多項(xiàng)式ln
vi polyexp(vi a);//多項(xiàng)式exp
vi operator / (vi a,vi b);//多項(xiàng)式除法
vi operator % (vi a,vi b);//多項(xiàng)式取模
vi polypow(vi a,int k);//多項(xiàng)式快速冪
int Sqrt(int x);//求x在模mod意義下的二次剩余
vi polysqrt(vi a);//多項(xiàng)式開(kāi)根
namespace eval_inter;//多點(diǎn)求值和快速插值
多項(xiàng)式求導(dǎo)和積分
vi Der(vi a){
For(i,1,(int)a.size()-1)
a[i-1]=(LL)a[i]*i%mod;
a.pop_back();
return a;
}
vi Int(vi a){
a.pb(0);
Fod(i,(int)a.size()-1,1)
a[i]=(LL)a[i-1]*Iv[i]%mod;
a[0]=0;
return a;
}
一些記號(hào)
為了方便，我們先聲明以下記號(hào)的含義：
多項(xiàng)式 \(A(x)\) 和其對(duì)應(yīng)的 \(i\) 次項(xiàng)系數(shù) \(a_i\)
多項(xiàng)式積分和求導(dǎo)
以及如下定義：
為了方便，在后面的推導(dǎo)中可能會(huì)簡(jiǎn)化多項(xiàng)式的表達(dá)，將 \(A(x)\) 簡(jiǎn)寫為 \(A\)，以及將 \(A_n(x)\) 簡(jiǎn)寫為 \(A_n\)。同樣地，為了方便，在采用這種簡(jiǎn)寫方式時(shí)，我可能會(huì)將 對(duì) \(x^?\) 取模的同余式 寫成等式，但是一般來(lái)說(shuō)意義仍是明確的。
多項(xiàng)式求逆
給定多項(xiàng)式 \(A(x)\) ，求出多項(xiàng)式 \(B(x)\) ，使得
其中多項(xiàng)式 \(A(x)\)、\(B(x)\) 只需要保留前 \(n\) 項(xiàng)（也就是 \(x^0\) 到 \(x^{n-1}\)）
做法
假設(shè)我們已經(jīng)得到了 \(B_n\)。
則
左右同除以 \(A\) ，得
因?yàn)槲覀冎?\(B_1(x) = a_0^{-1}\)，所以不難通過(guò)倍增法得到 \(B_n\)。
時(shí)間復(fù)雜度
示例代碼
vi polyinv(vi a){
int n=(int)a.size();
if (n==1)
return (vi){Pow(a[0],mod-2)};
vi b=polyinv(fix(a,(n+1)/2));
return fix(b*2-b*b*a,n);
}
這里有一個(gè)卡常技巧：如果我們已經(jīng)知道了 \(B_n\)，那么我們?cè)谧?b*b*a 時(shí)可以不關(guān)心前 \(n\) 位的系數(shù)，于是我們可以直接利用 dft 是循環(huán)卷積的性質(zhì)來(lái)縮小 dft 長(zhǎng)度。實(shí)現(xiàn)如下：
vi polyinv(vi a){
if (a.size()==1)
return vi(1,Pow(a[0],mod-2));
int n=a.size();
vi b=polyinv(fix(a,(n+1)/2));
int len=1<<(int)(log(n+(int)b.size())/log(2)+1);
vi c=fix(b,len),d=fix(a,len);
fft::init(len),FFT(&c[0],len,1),FFT(&d[0],len,1);
For(i,0,len-1)
c[i]=(LL)c[i]*c[i]%mod*d[i]%mod;
FFT(&c[0],len,-1);
b.resize(n);
For(i,(n+1)/2,n-1)
Del(b[i],c[i]);
return b;
}
多項(xiàng)式牛頓迭代
設(shè)有可導(dǎo)函數(shù) \(F(G)\) ，其中 \(G\) 是一個(gè)多項(xiàng)式。我們想要快速求其零點(diǎn)。
將 \(F(G)\) 泰勒展開(kāi)得到：
假設(shè) \(F(A)=0\)，那么我們來(lái)考慮怎么通過(guò)上式來(lái)由 \(A_n\) 導(dǎo)出 \(A_{2n}\)。
由于 \(A - A_n\) 的 \(0\cdots n-1\) 次項(xiàng)系數(shù)為 \(0\)，所以
這啟發(fā)我們使用倍增法來(lái)求一些關(guān)于多項(xiàng)式的函數(shù)。
多項(xiàng)式開(kāi)根
P.S. 這里需要求模意義下二次剩余，可以采用 BSGS 等算法解決。
給定多項(xiàng)式 \(A(x)\) ，求出多項(xiàng)式 \(B(x)\) 使得
做法
我們考慮套用牛頓迭代：
令 \(F(B) = B^2 - A\)，我們要求的便是 \(F(B)\) 的零點(diǎn)。則：
因?yàn)槲覀冎?/p>
所以這里我們可以使用任意求二次剩余的算法和倍增法解決多項(xiàng)式開(kāi)根問(wèn)題。
時(shí)間復(fù)雜度
示例代碼
vi polysqrt(vi a){
if (a.size()==1)
return vi(1,Sqrt(a[0]));
int n=a.size();
vi b=fix(polysqrt(fix(a,(n+1)/2)),n);
return fix((b+a*polyinv(b))*((mod+1)/2),n);
}
多項(xiàng)式對(duì)數(shù)函數(shù)
給定多項(xiàng)式 \(F(x)\)，求 \(\ln(F(x))\pmod{x^n}\) 。
做法
該問(wèn)題的解法由下式直接得出：
時(shí)間復(fù)雜度 $$O(n\log n)$$。
注意點(diǎn)
\(F(x)\) 的常數(shù)項(xiàng)必須是 \(1\) 。
否則設(shè) \(G(x)=kF(x)\) ，則 \(\ln(G(x))=\ln(F(x))+\ln(k)\) ，其中 \(\ln(k)\) 難以用模意義下的數(shù)來(lái)表示。
容易得知 \(\ln(F(x))\) 的常數(shù)項(xiàng)是 \(0\)，也就是說(shuō)，\(\ln(F(x))\) 相對(duì)于 \(F(x)\) 損失了常數(shù)項(xiàng)，而在高位上沒(méi)有損失。
示例代碼
vi polyln(vi a){
return Int(fix(Der(a)*polyinv(a),(int)a.size()-1));
}
多項(xiàng)式指數(shù)函數(shù)
給定多項(xiàng)式 \(F(x)\) ，求 \(e^{F(x)} \pmod{x^n}\) 。
做法
首先，設(shè)
則
設(shè)函數(shù) \(Q(x)=\ln(x) - F\) ，利用牛頓迭代得到：
時(shí)間復(fù)雜度仍然是
示例代碼
vi polyexp(vi a){
if (a.size()==1)
return vi(1,1);
int n=a.size();
vi b=polyexp(fix(a,(n+1)/2));
return fix(b+b*(a-polyln(fix(b,n))),n);
}
多項(xiàng)式快速冪
給定多項(xiàng)式 \(F(x)\) ，求 \(F^k(x)\pmod{x^n}\)。
做法
令 \(F(x)=bx^aG(x)\) ，其中 \(a,b\) 為常數(shù)，\(G(x)\) 的常數(shù)項(xiàng)為 1 。則
時(shí)間復(fù)雜度
注意點(diǎn)
若 \(k\) 極大（如洛谷的"多項(xiàng)式快速冪加強(qiáng)版"），則我們需要計(jì)算三個(gè)值：（為了表達(dá)清晰，這里用 \(p\) 表示模數(shù)）
那么
示例代碼
若保證了 \(f_0 = 1\)，則
vi polypow(vi a,int k){
return polyexp(polyln(a)*k);
}
否則：
vi polypow(vi a,int k){
// return polyexp(polyln(a)*k);
int p=0;
while (p<(int)a.size()&&!a[p])
p++;
if ((LL)p*k>=(int)a.size())
return vi();
vi b(a.begin()+p,a.end());
int coef=b[0],inv=Pow(coef,mod-2),powcoef=Pow(coef,k);
b=polyexp(polyln(b*inv)*k)*powcoef;
vi c(p*k+(int)b.size());
For(i,0,(int)b.size()-1)
c[i+p*k]=b[i];
return fix(c,a.size());
}
多項(xiàng)式除法
給定多項(xiàng)式 \(F(x),G(x)\) ，求多項(xiàng)式 \(Q(x)\)，使得
其中 \(F(x),G(x)\) 分別是 \(n,m\) 次多項(xiàng)式。
\(Q(x),R(x)\) 分別是 \(n-m+1,m-1\) 次多項(xiàng)式。
做法
定義 \(F^R(x)\) 表示多項(xiàng)式 \(F(x)\) 系數(shù)翻轉(zhuǎn)之后得到的結(jié)果。設(shè) \(F(x)\) 最高次項(xiàng)為 \(x^{n-1}\) ，則
于是可得
又因?yàn)?\(Q^R(x)\) 最高次項(xiàng)為 \(x^{n-m}\)，所以
時(shí)間復(fù)雜度
示例代碼
這里需要注意的是 \(m>n\) 要特判。
vi operator / (vi a,vi b){
int n=a.size(),m=b.size();
if (n<m)
return vi();
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
a=fix(fix(a,n-m+1)*polyinv(fix(b,n-m+1)),n-m+1);
reverse(a.begin(),a.end());
return a;
}
多項(xiàng)式取模
給定多項(xiàng)式 \(F(x),G(x)\) ，求多項(xiàng)式 \(R(x)\)，使得
其中 \(F(x),G(x)\) 分別是 \(n,m\) 次多項(xiàng)式。
\(Q(x),R(x)\) 分別是 \(n-m+1,m-1\) 次多項(xiàng)式。
做法
時(shí)間復(fù)雜度
示例代碼
vi operator % (vi a,vi b){
return fix(a-a/b*b,(int)b.size()-1);
}
多點(diǎn)求值與快速插值
多點(diǎn)求值
給定最高次項(xiàng)為 \(x^{m-1}\) 的函數(shù) \(F(x)\) ，以及 \(n\) 個(gè)參數(shù) \(x_{1\cdots n}\) ，求
做法
即多項(xiàng)式 \(F(x)\bmod (x-x_i)\) 的常數(shù)項(xiàng)。
設(shè)
則對(duì)于 \(i\leq n/2\) ，\(F(x_i)=(F\bmod L)(x_i)\) ；
對(duì)于 \(i> n/2\) ，\(F(x_i)=(F\bmod R)(x_i)\) ；
先預(yù)處理得到所有的 \(L(x)\) 和 \(R(x)\) ，然后再分治求出答案即可。
時(shí)間復(fù)雜度
快速插值
給定 \(n\) 對(duì) \((x_i,y_i)\) ，求最高次項(xiàng)為 \(x^{n-1}\) 的多項(xiàng)式 \(F(x)\) 滿足
做法
考慮拉格朗日插值法
令 \(M(x) = \prod_{i=1}^{n}(x-x_i)\)
令
根據(jù)洛必達(dá)法則，當(dāng) \(x\rightarrow x_i\) 時(shí)，
故
設(shè)
則
先預(yù)處理得到所有的 \(L(x)\) 和 \(R(x)\) ，然后再分治求出答案即可。
時(shí)間復(fù)雜度
示例代碼
namespace eval_inter{
int n;
vi f,x,y,prod[N*4];
void getprod(int rt,int L,int R){
if (L==R){
prod[rt]={Del(-x[L]),1};
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
getprod(ls,L,mid);
getprod(rs,mid+1,R);
prod[rt]=prod[ls]*prod[rs];
}
void gety(int rt,int L,int R,vi f){
f=fix(f%prod[rt],(int)prod[rt].size()-1);
if (L==R)
return (void)(y[L]=f[0]);
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
gety(ls,L,mid,f);
gety(rs,mid+1,R,f);
}
vi eval(vi _f,vi _x){
n=_x.size();
if (!n)
return vi();
f=_f,x=_x,y.resize(n);
getprod(1,0,n-1);
gety(1,0,n-1,f);
return y;
}
vi getf(int rt,int L,int R){
if (L==R)
return vi(1,y[L]);
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
return getf(ls,L,mid)*prod[rs]+getf(rs,mid+1,R)*prod[ls];
}
vi inter(vi _x,vi _y){
n=_x.size();
if (!n)
return vi();
x=_x,y.resize(n);
getprod(1,0,n-1);
vi M=Der(prod[1]);
gety(1,0,n-1,M);
For(i,0,n-1)
y[i]=(LL)_y[i]*Pow(y[i],mod-2)%mod;
return getf(1,0,n-1);
}
}
模板題
LOJ150 挑戰(zhàn)多項(xiàng)式
https://loj.ac/problem/150
浙公網(wǎng)安備 33010602011771號(hào)