1.求逆 设要对多项式A求逆，逆为B： 求在模ceil（n/2）的逆，将原式与之相减后平方，发现可得在模n意义下也是0了，然后两边同乘A，移项即可倍增了（注意此时A也是在模当前长度意义下的）。 最后倍增形式为B'=2*B-B*B*A  （b’等于2b减b方a），边界为常数取逆元，也可发现多项式有无逆取决于常数有无逆元 2.开根 与求逆类似，先求ceil（n/2）,然后将A移到左边使等式右边变成0，平方，加上4b^2a，再把右边b^2除到左边就发现ok了。 最终倍增形式：B'=(A+B*B)/2B(B'等于A加B方后除以2B），除法就上求逆，边界是常数开根，暴力枚举（并不会二次剩余...）？模板题保证是1... （开根里面套求逆，虽说复杂度仍然是nlog，但已经比大部分两个log慢了。。。）  3.Ln 两边求导得到所求的导数B’=A'/A，再积分即可。 4.Exp B=e^(A) 根据牛顿迭代的那套理论，设一个函数C，使C（B）=0，那么C(B)=LnB-A 假设已知在mod x^n的B0，要求在mod x^2n的B1 有C(B)=C(B0)/0!+C'(B0)/1!*(B-B0)+... 发现...可以省略，因为在mod x^n下B是唯一确定的，而mod x^2n下一定也满足mod x^n下，所以在mod x^2n时后面低的n位与mod x^n相等，当求的导数大于等于二阶发现（B-B0）那一项的幂次大于等于2，也就是最小的x项幂次大于等于2n，省略即可。 最终推得 B1=B0-C(B0)/C'(B0) 而C求导时是在把B0这个多项式看成变量求导（不要把每一项的x看成变量），A是已知多项式要看成一个常数 故B1=B0(1-Ln(B0)+A) 倍增即可。（注意能Exp一定要满足0次项为0，不然无法赋初值）   先贴4个的代码： #include #define ll long long using namespace std; const int mod=998244353; const int N=1e5+100; void Ad(int &x,int y) {if((x+=y)>=mod)x-=mod;} void Mul(int &x,int y) {x=1LL*x*y%mod;} int qpow(int x,int y) { int res=1; while(y) { if(y&1)res=1LL*res*x%mod; x=1LL*x*x%mod,y>>=1; } return res; } namespace Poly{ vectorA,B,C; int wh[N*3],cc,len,n,inv[N*3]; void Pre_Ntt(int l) { cc=0,len=1; while(len<=l)++cc,len<<=1; } void Cal_wh() {for(int i=1;i>1]>>1)|((i&1)<<(cc-1));} void Ntt(vector&a,bool inv) { for(int i=0;i>1,tp=qpow(3,(mod-1)/l); for(int i=0;i&b,int n) { if(n==1){b[0]=qpow(A[0],mod-2);return;} int md=(n+1)/2; vectora,c; Pre_Ntt(n+md+md),a.resize(len),c.resize(len); Get_Inv(c,md); Pre_Ntt(n+md+md),Cal_wh(); for(int i=0;i &a,vector &res,int n) { A=a,res.clear(),res.resize(n); Get_Inv(res,n); } void Get_Sqrt(vector&b,int n) { if(n==1){b[0]=1;return;} int md=(n+1)/2; vectora,c; Pre_Ntt(n+n),a.resize(len),c.resize(len); Get_Sqrt(c,md); for(int i=0;i &a,vector &res,int n) { Pre_Ntt(n+n); B=a,res.clear(),res.resize(len); Get_Sqrt(res,n); } void Dao(vector &a,vector &res,int n) { res.clear(),res.resize(n); for(int i=1;i &a,vector &res,int n) { res.clear(),res.resize(n+1),inv[1]=1; for(int i=2;i<=n;i++) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod; for(int i=n-1;i>=0;i--) res[i+1]=1LL*a[i]*inv[i+1]%mod; res[0]=0; } void Ln(vector&a,vector &res,int n) { static vectormo,ha; Dao(a,mo,n),Inv(a,ha,n); Pre_Ntt(n+n),Cal_wh(); mo.resize(len),Ntt(mo,0); ha.resize(len),Ntt(ha,0); for(int i=0;i&b1,int n) { if(n==1){b1[0]=1;return;} int md=(n+1)/2; vectorb0; b0.resize(n),b1.resize(n); Get_Exp(b0,md),Ln(b0,b1,n); for(int i=0;i&a,vector &res,int n) {C=a,res.resize(n),Get_Exp(res,n);} } int main() { int n; scanf("%d",&n); vectora,b; a.resize(n); for(int i=0;i