• 最近學習了多項式的求逆、取模和多點求值，這些方法能夠解決很多多項式問題。

• 這三個操作是環環相扣的，很有趣，學完后不妨記錄一下。

多項式求逆

• 給出一個次數界為 $n$ 的多項式 $A(x)$ ，需要求 $B(x)$ 滿足： $$A(x)B(x)\equiv 1(mod{x}^n)$$

• 我們考慮倍增來求解，假設我們已經知道 $G(x)$ 滿足：$$A(x)G(x)\equiv 1(mod{x}^{?\frac{n}{2}?})$$

• 那么開始推導，兩式相減：$$B(x)?G(x)\equiv 0(mod{x}^{?\frac{n}{2}?})$$

• 兩邊平方：$$B(x{)}^2+G(x{)}^2?2G(x)B(x)\equiv 0(mod{x}^n)$$

• 兩邊同乘 $A(x)$ ：$$B(x)+A(x)G(x{)}^2?2G(x)\equiv 0(mod{x}^n)$$

• 于是可求得 $B(x)$ ：$$B(x)\equiv 2G(x)?A(x)G(x{)}^2(mod{x}^n)$$

• 當遞歸至 $n=1$ 時則有：$$B(0)=A(0{)}^{?1}$$

• 那么我們開始時就次數界 $n$ 配成 $2^k$ 的形式，直接做倍增即可完成求逆。

• 時間復雜度 $O(nlogn)$ 。

• 模板題：洛谷 P4238 【模板】多項式求逆

多項式取模

• 多項式取模是依賴于多項式求逆的。

• 給出一個次數為 $n$ 的多項式 $A(x)$ ，一個次數為 $m(m\le n)$ 的多項式 $B(x)$。

• 我們需要求出多項式 $C(x)$ 和 $R(x)$ 滿足：$$A(x)=B(x)C(x)+R(x)(?)$$

• 其中 $C(x)$ 的次數 $\le n?m$ ，$R(x)$ 的次數 $<m$ 。

• 考慮一個翻轉操作：$$A^R(x)=x^{n}A(\frac{1}{x})$$

• 其實質就是多項式的系數翻轉過來。

• 將 $(?)$ 式兩邊同乘 $x^n$ 、并令 $x=\frac{1}{x}$ 代入，可得：$$x^{n}A(\frac{1}{x})=x^{m}B(\frac{1}{x})?x^{n?m}C(\frac{1}{x})+x^{n?m+1}{x}^{m?1}R(\frac{1}{x})$$

• 則有：$$A^R(x)=B^R(x)C^R(x)+x^{n?m+1}{R}^R(x)$$

• 關鍵一步來了，把上式放在 $(mod{x}^{n?m+1})$ 下，就能消除 $R^R(x)$ 的影響（并且對 $C^R(x)$ 無影響，其每一項次數都 $\le n?m$）：$$A^R(x)\equiv B^R(x)C^R(x)(mod{x}^{n?m+1})$$

• 于是我們通過多項式求逆可以算出 $C^R(x)$ ：$$C^R(x)\equiv \frac{A^R(x)}{B^R(x)}(mod{x}^{n?m+1})$$

• 之后翻轉得到 $C(x)$ ，回代 $(?)$ 式求出 $R(x)$ 即可！

• 以上各操作均是 $O(nlogn)$ 的。

• 模板題：洛谷 P4512 【模板】多項式除法

多項式多點求值

• 多點求值需要用到多項式取模！

• 給出一個 $n$ 次多項式 $F(x)$ ，和 $m$ 個值 $x_1,x_2,???,x_m$ ，要求 $F(x_1),F(x_2),???,F(x_m)$ 。

• 比較關鍵的一個性質：$$F(x)mod(x?a)=F(a)$$

• 用因式定理或者直接將 $(x?a+a{)}^k$ 二項式展開都能很容易得到。

• 那么我們依據這個來分治解決本問題。

• 令 $L(x)={\sum }_{i=1}^{?\frac{n}{2}?}(x?x_i)$ ，$R(x)={\sum }_{i=?\frac{n}{2}?+1}^n(x?x_i)$ ，

• 那么對于 $1\le i\le ?\frac{n}{2}?$ ，$F(x_i)=(FmodL)(x_i)$ ；對于 $?\frac{n}{2}?+1\le i\le n$ ，$F(x_i)=(FmodR)(x_i)$。（原理同上述性質）

• 于是我們向線段樹一樣往下分治計算即可。

• 具體來說就是先預處理出每個區間的 ${\prod }_{i=l}^r(x?x_i)$ （相當于是求出 $L,R$ ，自下而上），

• 之后再自上而下地把 $F(x)$ 往下傳，每次就模 $L$ 或 $R$ 并分別傳向左右子區間。

• 當分治到底層（$l=r$）的時候，$F(x)$ 就是被模剩一個常數項 $F^{\prime }(0)$ 了，直接就有 $F(x_i)=F^{\prime }(0)$ 。

• 每次做多項式取模是 $O(nlogn)$ 的，套上分治就是 $O(nlo{g}^{2}n)$ 的了。當然常數很大……

• 模板題：洛谷 P5050 【模板】多項式多點求值

• 這里給出這題的代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; typedef long long LL; const int N=64005,M=16,G=3,mo=998244353; int tot; int f[N],p[N],ans[N]; int mul[N*M<<1],st[N<<2],en[N<<2]; int g[N*M<<1],stg[N<<2],eng[N<<2]; int a[N],b[N],c[N],rr[N];//a=b*c+rr int ra[N],rb[N<<1],irb[N<<2]; int f1[N<<2],f2[N<<2],rev[N<<2],wn[N<<2]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int ksm(int x,int y) {int s=1;while(y){if(y&1) s=(LL)s*x%mo;x=(LL)x*x%mo;y>>=1;}return s; } inline void NTT(int *y,int len,int ff) {for(int i=0;i<len;i++)if(i<rev[i]) swap(y[i],y[rev[i]]);for(int h=2,d=len>>1;h<=len;h<<=1,d>>=1)for(int i=0,k=h>>1;i<len;i+=h)for(int j=0,cnt=0;j<k;j++,cnt+=d){int u=y[i+j],t=(LL)wn[cnt]*y[i+j+k]%mo;y[i+j]=u+t>=mo?u+t-mo:u+t;y[i+j+k]=u-t<0?u-t+mo:u-t;}if(ff==-1){for(int i=len>>1;i;i--) swap(y[i],y[len-i]);int inv=ksm(len,mo-2);for(int i=0;i<len;i++) y[i]=(LL)y[i]*inv%mo;} } void solve(int len,int num) {if(len==1){irb[0]=ksm(rb[0],mo-2);return;}solve(len>>1,num-1);for(int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|(i&1)<<num-1;int w0=ksm(G,(mo-1)/len);for(int i=wn[0]=1;i<=len;i++) wn[i]=(LL)wn[i-1]*w0%mo;for(int i=0;i<len>>1;i++) f1[i]=rb[i];NTT(f1,len,1),NTT(irb,len,1);for(int i=0;i<len;i++) f1[i]=(2-(LL)f1[i]*irb[i]%mo+mo)*irb[i]%mo;NTT(f1,len,-1);for(int i=0;i<len>>1;i++) irb[i]=f1[i];for(int i=len>>1;i<len;i++) irb[i]=0; } void make(int v,int l,int r) {if(l==r){st[v]=++tot;mul[tot]=mo-p[l];en[v]=++tot;mul[tot]=1;return;}int mid=l+r>>1,ls=v<<1,rs=ls|1;make(ls,l,mid);make(rs,mid+1,r);int na=en[ls]-st[ls]+1,nb=en[rs]-st[rs]+1;int len=1,ll=0;while(len<na+nb) len<<=1,ll++;for(int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|(i&1)<<ll-1;int w0=ksm(G,(mo-1)/len);for(int i=wn[0]=1;i<=len;i++) wn[i]=(LL)wn[i-1]*w0%mo;for(int i=0;i<na;i++) f1[i]=mul[st[ls]+i];for(int i=na;i<len;i++) f1[i]=0;for(int i=0;i<nb;i++) f2[i]=mul[st[rs]+i];for(int i=nb;i<len;i++) f2[i]=0;NTT(f1,len,1),NTT(f2,len,1);for(int i=0;i<len;i++) f1[i]=(LL)f1[i]*f2[i]%mo;NTT(f1,len,-1);na+=nb;while(na>1 && !f1[na-1]) na--;st[v]=tot+1;for(int i=0;i<na;i++) mul[++tot]=f1[i];en[v]=tot; } void find(int v,int l,int r,int fa) {int na=eng[fa]-stg[fa],nb=en[v]-st[v];if(na>=nb){for(int i=0;i<=na;i++) a[i]=g[stg[fa]+i];for(int i=0;i<=nb;i++) b[i]=mul[st[v]+i];for(int i=0;i<=na-nb;i++) ra[i]=a[na-i];for(int i=0;i<=nb;i++) rb[i]=b[nb-i];for(int i=na-nb+1;i<=nb;i++) rb[i]=0;int len=1,ll=0;while(len<(na-nb+1)*2) len<<=1,ll++;for(int i=0;i<len;i++) f1[i]=0;solve(len,ll);for(int i=0;i<=na-nb;i++) f1[i]=ra[i],f2[i]=irb[i];for(int i=na-nb+1;i<len;i++) f1[i]=f2[i]=0;NTT(f1,len,1),NTT(f2,len,1);for(int i=0;i<len;i++) f1[i]=(LL)f1[i]*f2[i]%mo;NTT(f1,len,-1);for(int i=0;i<=na-nb;i++) c[na-nb-i]=f1[i];len=1,ll=0;while(len<nb<<1) len<<=1,ll++;for(int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|(i&1)<<ll-1;int w0=ksm(G,(mo-1)/len);for(int i=wn[0]=1;i<=len;i++) wn[i]=(LL)wn[i-1]*w0%mo;for(int i=0;i<nb;i++) f1[i]=b[i],f2[i]=c[i];for(int i=nb;i<len;i++) f1[i]=f2[i]=0;NTT(f1,len,1),NTT(f2,len,1);for(int i=0;i<len;i++) f1[i]=(LL)f1[i]*f2[i]%mo;NTT(f1,len,-1);for(int i=0;i<nb;i++) rr[i]=(a[i]-f1[i]+mo)%mo;for(int i=0;i<=max(na,nb);i++) a[i]=b[i]=c[i]=ra[i]=rb[i]=irb[i]=0;while(nb>1 && !rr[nb-1]) nb--;stg[v]=tot+1;for(int i=0;i<nb;i++) g[++tot]=rr[i],rr[i]=0;eng[v]=tot;}else{stg[v]=tot+1;for(int i=stg[fa];i<=eng[fa];i++) g[++tot]=g[i];eng[v]=tot;}if(l==r){ans[l]=g[stg[v]];return;}int mid=l+r>>1;find(v<<1,l,mid,v);find(v<<1|1,mid+1,r,v); } int main() {int n=read(),m=read();for(int i=0;i<=n;i++) f[i]=read();for(int i=1;i<=m;i++) p[i]=read();make(1,1,m);stg[tot=0]=1;for(int i=0;i<=n;i++) g[++tot]=f[i];eng[0]=tot;find(1,1,m,0);for(int i=1;i<=m;i++) write(ans[i]),putchar('\n');return 0; }

總結

以上是生活随笔為你收集整理的多项式的求逆、取模和多点求值学习小记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。