class="markdown_views prism-atom-one-light">

迭代法求零点

已知$f$是一个多项式对多项式的函数，现要逼近f的零点，采用倍增法： 假如要求A模$x^n$意义下的值，则预先求出A0为A模$x^{n/2}$意义下的值
由泰勒展开，$f(A)=f(A0)+f'(A0)(A-A0)$在模$x^n$意义下成立。令$f(A)=0$，化简后：
$A=A0-frac {f(A0)} {f'(A0)}$
（牛顿迭代的式子）
由此式可求出A在模$x^n$意义下的值。

推求逆

求D的逆，令$f(x)=frac 1 x - D$即可

推开方

令$f(x)=x^2-D$即可

推exp

令$f(x)=ln x-D$即可。
注意此时，由于上式泰勒展开是对多项式x进行的，因此$ln x$的导数直接就是$1/x$

推ln

这个和迭代没啥关系
先求其导函数，再求其积分
注意此时是对数x求导，而不是多项式，所以是复合函数求导。 $ln' F(x)=frac {F'(x)} {F(x)}$
计算出上式后积分即可。
求ln时要保证给定多项式常数项为1，最后结果常数项默认为0。

积分、求导

O(n)计算即可。积分的常数项视作0. 板子 #include #include #include #include using namespace std; typedef long long ll; const int mo=998244353,N=1e6+10000; int cnt[N],n,m,Mx,mx; ll g[N],w[N],iw[N],jc[N],njc[N],ans[N],inv[N]; ll ksm(ll x,ll y){ ll ret=1;for(;y;y>>=1){ if(y&1)ret=ret*x%mo; x=x*x%mo; } return ret; } int h[N]; void dft(ll *a,int sz,int sig){ for(int i=0;i<sz;i++){ h[i]=(h[i>>1]>>1)+(sz>>1)*(i&1); if(h[i]<i)swap(a[i],a[h[i]]); } for(int m=2;m<=sz;m<<=1){ int hf=m>>1,step=Mx/m; for(int i=0;i<sz;i+=m){ for(int j=0;j<hf;j++){ ll T=a[i+j+hf]*(sig==1?w[j*step]:iw[j*step])%mo; a[i+j+hf]=(a[i+j]-T)%mo; a[i+j]=(a[i+j]+T)%mo; } } } if(sig==-1){ ll ny=ksm(sz,mo-2); for(int i=0;i<sz;i++)a[i]=a[i]*ny%mo; } } ll ZZ[N],TT[N]; void getinv(ll *T,ll *Z,int sz){ memset(T,0,sz*8*2); memset(TT,0,sz*8*2); memset(ZZ,0,sz*8*2); T[0]=ksm(Z[0],mo-2); for(int r=2;r<=sz;r<<=1){ memcpy(TT,T,r*8); dft(TT,2*r,1); memcpy(ZZ,Z,r*8); dft(ZZ,2*r,1); for(int i=0;i<2*r;i++)T[i]=TT[i]*(2-ZZ[i]*TT[i]%mo)%mo; dft(T,2*r,-1); for(int i=r;i<2*r;i++)T[i]=0; } } void qiudao(ll *a,int sz){ for(int i=0;i<sz;i++) a[i]=a[i+1]*(i+1)%mo; } void jifen(ll *a,int sz){ for(int i=sz-1;i;i--)a[i]=a[i-1]*inv[i]%mo; a[0]=0; } ll OO[N]; void getln(ll *U,ll *O,int sz){ memset(U,0,sz*8*2); memcpy(U,O,sz*8); qiudao(U,sz); getinv(OO,O,sz); dft(U,sz*2,1); dft(OO,sz*2,1); for(int i=0;i<sz*2;i++)U[i]=U[i]*OO[i]%mo; dft(U,sz*2,-1); for(int i=sz;i<2*sz;i++)U[i]=0; jifen(U,sz); } ll lnd[N],DD[N],SS[N]; void getexp(ll *D,ll *S,int sz){ memset(D,0,sz*8*2); memset(DD,0,sz*8*2); memset(SS,0,sz*8*2); memset(lnd,0,sz*8*2); D[0]=1; for(int r=2;r<=sz;r<<=1){ getln(lnd,D,r); for(int i=0;i<r;i++)lnd[i]=(-lnd[i]+S[i])%mo; lnd[0]++; dft(lnd,2*r,1); memcpy(DD,D,8*r); dft(DD,2*r,1); for(int i=0;i<2*r;i++) D[i]=DD[i]*lnd[i]%mo; dft(D,2*r,-1); for(int i=r;i<2*r;i++)D[i]=0; } } ll TE[N]; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++){ int x;scanf("%d",&x);cnt[x]++; } for(int i=1;i<=m;i++)if(cnt[i]){ for(int j=i;j<=m;j+=i){ g[j-1]=(g[j-1]+i*cnt[i])%mo; } } for(Mx=1;Mx<=m*2;Mx<<=1); w[0]=iw[0]=1;w[1]=ksm(3,(mo-1)/Mx); iw[1]=ksm(w[1],mo-2); for(int i=2;i<Mx;i++){ w[i]=w[i-1]*w[1]%mo,iw[i]=iw[i-1]*iw[1]%mo; } jc[0]=1;for(int i=1;i<=m;i++)jc[i]=jc[i-1]*i%mo; njc[m]=ksm(jc[m],mo-2); for(int i=m-1;~i;i--)njc[i]=njc[i+1]*(i+1)%mo; for(int i=1;i<=m;i++)inv[i]=njc[i]*jc[i-1]%mo; jifen(g,m+1); getexp(ans,g,Mx>>1); for(int i=1;i<=m;i++)printf("%lld ",(ans[i]+