因为目前半家桶里只会俩所以就成四分之一了。
多项式乘法逆
设多项式 \(A(x)\) 为 \(n\) 次多项式，求多项式 \(B\) ，使 \(A(x)*B(x)\equiv 1(\mod x^n)\) 。
设 \(A(x)*C(x)\equiv 1(\mod x^{\left\lceil\frac{n}{2}\right\rceil})\) ，那么
\[A(x)*B(x)\equiv 1(\mod x^n)\to A(x)*B(x)\equiv 1(\mod x^{\left\lceil\frac{n}{2}\right\rceil})\\ \; \\A(x)*(B(x)-C(x))\equiv 0(\mod x^{\left\lceil\frac{n}{2}\right\rceil})\\ \; \\B(x)-C(x)\equiv 0(\mod x^{\left\lceil\frac{n}{2}\right\rceil})\to (B(x)-C(x))^2\equiv 0(\mod x^n)\\ \; \\B^2(x)-2B(x)C(x)+C^2(x)\equiv 0(\mod x^n)\\ \; \\B(x)-2C(x)+A(x)C^2(x)\equiv 0(\mod x^n)\to B(x)\equiv2C(x)+A(x)C^2(x)(\mod x^n) \]递归求解。由主定理复杂度 \(O(n\log n)\) 。
洛谷P4238[模板]多项式乘法逆
#include<bits/stdc++.h>
using namespace std;
namespace IO{
typedef long long LL;
int read(){
int x=0,f=0; char ch=getchar();
while(ch<'0'||ch>'9'){ f|=ch=='-'; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return f?-x:x;
} char outp[50];
void write(int x,char sp,int len=0){
if(x<0) putchar('-'), x=-x;
do{ outp[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(outp[i]); putchar(sp);
}
void ckmin(int& x,int y){ x=x<y?x:y; }
void ckmax(int& x,int y){ x=x>y?x:y; }
} using namespace IO;
const int NN=400010,mod=998244353;
int n;
namespace Poly_Calculation{
const LL rt=3,two=998244355;
int l,len,r[NN];
LL a[NN],b[NN],g[NN],tp[NN];
void pls(LL& x,LL y){ (x+=y)>=mod?(x-=mod):(x<0?(x+=mod):0); }
LL qpow(LL a,int b=mod-2,LL res=1){
for(;b;b>>=1,a=a*a%mod)
if(b&1) res=res*a%mod;
return res;
}
void prework(int n){
for(len=1,l=0;len<=n+n;len<<=1) ++l;
for(int i=0;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
g[0]=1; g[1]=qpow(rt,(mod-1)/len);
for(int i=2;i<len;i++) g[i]=g[i-1]*g[1]%mod;
}
void ntt(LL* a,int n){
for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
for(int t=n>>1,d=1;d<n;d<<=1,t>>=1)
for(int i=0;i<n;i+=(d<<1)) for(int j=0;j<d;j++){
LL tmp=g[j*t]*a[i+j+d]%mod;
pls(a[i+j+d]=a[i+j],-tmp); pls(a[i+j],tmp);
}
}
void polyinv(LL* a,LL* res,int deg){
if(deg==1) return void(res[0]=qpow(a[0]));
polyinv(a,res,deg+1>>1); prework(deg);
for(int i=0;i<deg;i++) tp[i]=a[i];
for(int i=deg;i<len;i++) tp[i]=0;
ntt(res,len); ntt(tp,len);
for(int i=0;i<len;i++) res[i]=(two-res[i]*tp[i]%mod)*res[i]%mod, g[i]=qpow(g[i]);
ntt(res,len); LL inv=qpow(len);
for(int i=0;i<deg;i++) res[i]=res[i]*inv%mod;
for(int i=deg;i<len;i++) res[i]=0;
}
} using namespace Poly_Calculation;
signed main(){
n=read();
for(int i=0;i<n;i++) a[i]=read();
polyinv(a,b,n);
for(int i=0;i<n;i++) write(b[i],' ');
return puts(""),0;
}
多项式开根
已知 \(n\) 多项式 \(A(x)\) ，求多项式 \(B(x)\) ，满足 \(B^2(x)\equiv A(x)(\mod x^n)\) 。
类似地，设 \(C^2(x)\equiv A(x)(\mod x^{\left\lceil\frac{n}{2}\right\rceil})\) ，那么
\[B(x)\equiv C(x)(\mod x^{\left\lceil\frac{n}{2}\right\rceil})\\ \; \\B(x)-C(x)\equiv 0(\mod x^{\left\lceil\frac{n}{2}\right\rceil})\to (B(x)-C(x))^2\equiv 0(\mod x^n)\\ \; \\B^2(x)-2B(x)C(x)+C^2(x)\equiv 0(\mod x^n)\\ \; \\A(x)-2B(x)C(x)+C^2(x)\equiv 0(\mod 0)\\ \; \\B(x)=\equiv\frac{C(x)+\frac{A(x)}{C(x)}}{2}(\mod x^n) \]递归并求逆求解。
这份板子因为某种神秘力量常数过丑了。有时间的话应该会来改改吧。（
洛谷P5205[模板]多项式开根
#include<bits/stdc++.h>
using namespace std;
namespace IO{
typedef long long LL;
int read(){
int x=0,f=0; char ch=getchar();
while(ch<'0'||ch>'9'){ f|=ch=='-'; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return f?-x:x;
} char outp[50];
void write(int x,char sp,int len=0){
if(x<0) putchar('-'), x=-x;
do{ outp[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(outp[i]); putchar(sp);
}
void ckmin(int& x,int y){ x=x<y?x:y; }
void ckmax(int& x,int y){ x=x>y?x:y; }
} using namespace IO;
const int NN=400010,mod=998244353;
int n;
namespace Poly_Calculation{
const LL rt=3,two=998244355,inv2=499122177;
int l,len,r[NN];
LL a[NN],b[NN],g[NN],iv[NN],tp[NN];
void pls(LL& x,LL y){ (x+=y)>=mod?(x-=mod):(x<0?(x+=mod):0); }
LL qpow(LL a,int b=mod-2,LL res=1){
for(;b;b>>=1,a=a*a%mod)
if(b&1) res=res*a%mod;
return res;
}
void prework(int n){
for(len=1,l=0;len<=n+n;len<<=1) ++l;
for(int i=0;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
g[0]=1; g[1]=qpow(rt,(mod-1)/len);
for(int i=2;i<len;i++) g[i]=g[i-1]*g[1]%mod;
}
void ntt(LL* a,int n){
for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
for(int t=n>>1,d=1;d<n;d<<=1,t>>=1)
for(int i=0;i<n;i+=(d<<1)) for(int j=0;j<d;j++){
LL tmp=g[j*t]*a[i+j+d]%mod;
pls(a[i+j+d]=a[i+j],-tmp); pls(a[i+j],tmp);
}
}
void polyinv(LL* a,LL* res,int deg){
if(deg==1) return void(res[0]=qpow(a[0]));
polyinv(a,res,deg+1>>1); prework(deg);
for(int i=0;i<deg;i++) tp[i]=a[i];
ntt(res,len); ntt(tp,len);
for(int i=0;i<len;i++) res[i]=(two-res[i]*tp[i]%mod)*res[i]%mod, g[i]=qpow(g[i]);
ntt(res,len); LL inv=qpow(len);
for(int i=0;i<deg;i++) res[i]=res[i]*inv%mod, tp[i]=0;;
for(int i=deg;i<len;i++) res[i]=tp[i]=0;
}
void polysqr(LL* a,LL* res,int deg){
if(deg==1) return void(res[0]=1);
polysqr(a,res,deg+1>>1);
polyinv(res,iv,deg); prework(deg);
for(int i=0;i<deg;i++) tp[i]=a[i];
ntt(res,len); ntt(iv,len); ntt(tp,len);
for(int i=0;i<len;i++) res[i]=(tp[i]*iv[i]%mod+res[i])*inv2%mod, g[i]=qpow(g[i]);
ntt(res,len); LL inv=qpow(len);
for(int i=0;i<deg;i++) res[i]=res[i]*inv%mod, iv[i]=tp[i]=0;
for(int i=deg;i<len;i++) res[i]=iv[i]=tp[i]=0;
}
} using namespace Poly_Calculation;
signed main(){
n=read();
for(int i=0;i<n;i++) a[i]=read();
polysqr(a,b,n);
for(int i=0;i<n;i++) write(b[i],' ');
return puts(""),0;
}