题解 P5205 【【模板】多项式开根】

Owen_codeisking

2019-01-29 14:54:16

Solution

看到新模板,过来做一下。 ### 前置知识:多项式求逆 + $NTT$ 设 $H^2(x)\equiv F(x)(mod\ x^{\lceil\frac n2 \rceil})$ $G(x)\equiv H(x)(mod\ x^{\lceil\frac n2 \rceil})$ $G(x)-H(x)\equiv 0(mod\ x^{\lceil\frac n2 \rceil})$ $(G(x)-H(x))^2\equiv 0(mod\ x^{\lceil\frac n2 \rceil})$ $G^2(x)-2H(x)*G(x)+H^2(x)\equiv 0(mod\ x^n)$ $F(x)-2H(x)*G(x)+H^2(x)\equiv 0(mod\ x^n)$ $G(x)=\Large \frac {F(x)+H^2(x)}{2H(x)}$ 对上述式子进行多项式求逆 + $NTT$ 即可 $Code\ Below:$ ```cpp #include <bits/stdc++.h> using namespace std; const int maxn=400000+10; const int mod=998244353; const int inv2=499122177; int n,f[maxn],g[maxn],A[maxn],B[maxn],C[maxn],D[maxn],r[maxn]; inline int read(){ register int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return (f==1)?x:-x; } int fpow(int a,int b){ int ret=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ret=1ll*ret*a%mod; return ret; } void NTT(int *f,int n,int op){ for(int i=0;i<n;i++) if(i<r[i]) swap(f[i],f[r[i]]); int buf,tmp,x,y; for(int len=1;len<n;len<<=1){ tmp=fpow(3,(mod-1)/(len<<1)); if(op==-1) tmp=fpow(tmp,mod-2); for(int i=0;i<n;i+=len<<1){ buf=1; for(int j=0;j<len;j++){ x=f[i+j];y=1ll*buf*f[i+j+len]%mod; f[i+j]=(x+y)%mod;f[i+j+len]=(x-y+mod)%mod; buf=1ll*buf*tmp%mod; } } } if(op==1) return ; int inv=fpow(n,mod-2); for(int i=0;i<n;i++) f[i]=1ll*f[i]*inv%mod; } void Inv(int *a,int *b,int n){ b[0]=fpow(a[0],mod-2); int len,lim; for(len=1;len<(n<<1);len<<=1){ lim=len<<1; for(int i=0;i<len;i++) A[i]=a[i],B[i]=b[i]; for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)?len:0); NTT(A,lim,1);NTT(B,lim,1); for(int i=0;i<lim;i++) b[i]=((2ll-1ll*A[i]*B[i]%mod)*B[i]%mod+mod)%mod; NTT(b,lim,-1); for(int i=len;i<lim;i++) b[i]=0; } for(int i=0;i<len;i++) A[i]=B[i]=0; for(int i=n;i<len;i++) b[i]=0; } void Sqrt(int *a,int *b,int n){ b[0]=1; int *A=C,*B=D,len,lim; for(len=1;len<(n<<1);len<<=1){ lim=len<<1; for(int i=0;i<len;i++) A[i]=a[i]; Inv(b,B,lim>>1); for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)?len:0); NTT(A,lim,1);NTT(B,lim,1); for(int i=0;i<lim;i++) A[i]=1ll*A[i]*B[i]%mod; NTT(A,lim,-1); for(int i=0;i<len;i++) b[i]=1ll*(b[i]+A[i])%mod*inv2%mod; for(int i=len;i<lim;i++) b[i]=0; } for(int i=0;i<len;i++) A[i]=B[i]=0; for(int i=n;i<len;i++) b[i]=0; } int main() { n=read(); for(int i=0;i<n;i++) f[i]=read(); Sqrt(f,g,n); for(int i=0;i<n;i++) printf("%d ",g[i]); printf("\n"); return 0; } ```