多项式求逆元模板

2019-04-13 13:33发布

站内文章 / 模拟电子
12679 0 1618
多项式求逆元具体概念及求法可见这里，本文主要提供模板。 本文提供的是模998244353下保留0~n次项，即mod(xn+1)意义下的模板。 #include #define ll long long using namespace std; int getint() { int i=0,f=1;char c; for(c=getchar();c!='-'&&(c<'0'||c>'9');c=getchar()); if(c=='-')f=-1,c=getchar(); for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0'; return i*f; } const int N=500005,p=998244353,g=3; int n,a[N],b[N],pos[N],w[N],inv[N]; int Pow(int x,int y) { int res=1; for(;y;y>>=1,x=(ll)x*x%p) if(y&1)res=(ll)res*x%p; return res; } void Init() { int len=1,num=0; while(len<((n+1)<<1)) { len<<=1; w[++num]=Pow(g,(p-1)/len); inv[num]=Pow(w[num],p-2); } } void NTT(int f[],int len,int on) { for(int i=1;ipos[i]=(i&1)?pos[i>>1]>>1|(len>>1):pos[i>>1]>>1; for(int i=1;iif(i<pos[i])swap(f[i],f[pos[i]]); for(int i=1,num=1;i1,num++) { int wn=(on==1?w[num]:inv[num]); for(int j=0;j1)) { int wi=1; for(int k=j;kint u=f[k],v=(ll)wi*f[k+i]%p; f[k]=(u+v)%p,f[k+i]=(u-v+p)%p; wi=(ll)wi*wn%p; } } } if(on==-1) for(int i=0;i*Pow(len,p-2)%p; } void Poly_inv(int a[],int b[],int deg) { if(deg==1) { b[0]=Pow(a[0],p-2); return; } Poly_inv(a,b,(deg+1)>>1); static int tmp[N]; int len=1; while(len<(deg<<1))len<<=1; for(int i=0;ifor(int i=deg;i0; for(int i=(deg+1)>>1;i0; NTT(tmp,len,1),NTT(b,len,1); for(int i=0;i*((2-(ll)tmp[i]*b[i]%p+p)%p)%p; NTT(b,len,-1); } int main() { //freopen("lx.in","r",stdin); n=getint(); Init(); for(int i=0;i<=n;i++)a[i]=getint(); Poly_inv(a,b,n+1); for(int i=0;i<=n;i++)cout<' '; return 0; }

热门文章