设已知A(x)B(x)=1(mod x^n)，考虑A(x)C(x)=1(mod x^2n)
显然B(x)-C(x)=0(mod x^n)
平方得B(x)^2-2B(x)C(x)+C(x)^2=0(mod x^2n)
同乘A(x)得A(x)B(x)^2-2B(x)+C(x)=0(mod x^2n)
即有C(x)=2B(x)-A(x)B(x)^2，fft即可
设A(x)常数项为t，则A(x)*1/t=1(mod x^1)/
不断倍增即可解决
注意fft又是循环卷积，实现的时候必须做适当的清零
然后每个式子在不全相同的模意义下成立，清零的区间是哪段也要注意一下
代码：
#include<cstdio>namespace poly{ #define mo 998244353 struct AwD{int x;}; AwD Operator+(AwD a,AwD b){return (AwD){(a.x+b.x)%mo};} AwD operator-(AwD a,AwD b){return (AwD){(a.x-b.x+mo)%mo};} AwD operator*(AwD a,AwD b){return (AwD){(int)(1LL*a.x*b.x%mo)};} AwD operator^(AwD a,int b){if(b<0) b+=mo-1;if(!b) return (AwD){1};AwD temp=a^(b>>1);temp=temp*temp;if(b&1) temp=temp*a;return temp;} AwD operator/(AwD a,AwD b){return a*(b^-1);} const AwD root=(AwD){3}; const int om=mo-1; void ntt(AwD*a,int n,int d){ int i,j,k; AwD w,t,u,v; for(i=(n>>1),j=1;j<n;j++){ if(i<j) t=a[i],a[i]=a[j],a[j]=t; for(k=(n>>1);i&k;i^=k,k>>=1);i^=k; } for(k=2;k<=n;k<<=1){ w=root^((mo-1)/k*d); for(i=0;i<n;i+=k){ t=(AwD){1}; for(j=i;j<i+(k>>1);j++){ u=a[j];v=t*a[j+(k>>1)]; a[j]=u+v;a[j+(k>>1)]=u-v;t=t*w; } } } } AwD a[1<<20],b[1<<20]; void PRint(AwD*a,int l){ for(int i=0;i<l;i++) printf("%d ",a[i].x); printf("/n"); } void plus(AwD*_a,AwD*_b,int l,AwD*c){ for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i]; for(int i=0;i<l;i++) c[i]=a[i]+b[i]; } void subt(AwD*_a,AwD*_b,int l,AwD*c){ for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i]; for(int i=0;i<l;i++) c[i]=a[i]-b[i]; } void mult(AwD*_a,AwD b,int l,AwD*c){ for(int i=0;i<l;i++) a[i]=_a[i]; for(int i=0;i<l;i++) c[i]=a[i]*b; } void mult(AwD*_a,AwD*_b,int l,AwD*c){ for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i]; ntt(a,l,1);ntt(b,l,1); for(int i=0;i<l;i++) c[i]=a[i]*b[i]; ntt(c,l,-1); for(int i=0;i<l;i++) c[i]=c[i]/(AwD){l}; } AwD a1[1<<20],aa[1<<20],tmp[1<<20]; void inv(AwD*_a,int l,AwD*b){ for(int i=0;i<l;i++) a1[i]=_a[i]; for(int i=0;i<l;i++) b[i]=i?(AwD){0}:a1[i]^-1; for(int l0=2;l0<=l;l0<<=1){ mult(b,(AwD){2},l0>>1,tmp); mult(b,b,l0,b); for(int i=0;i<(l0<<1);i++) aa[i]=i<l0?a1[i]:(AwD){0}; mult(aa,b,l0<<1,b); for(int i=l0;i<(l0<<1);i++) b[i]=(AwD){0}; subt(tmp,b,l0,b); } }}int n,l;poly::AwD a[1<<20];int main(){ scanf("%d",&n);n++; for(int i=0;i<n;i++) scanf("%d",&a[i].x); l=1;while(l<n) l<<=1;for(int i=n;i<l;i++) a[i].x=0; poly::inv(a,l,a); for(int i=0;i<n;i++) printf("%d ",a[i].x);}新闻热点
疑难解答
