还是倍增思想
每一层 还要套一个多项式求逆
所以O(nlog^2n)，常数也不小
数组比较多
再trick一下
得到：
$T=(T‘+F*inv(T‘))*inv2$
可以只算一次多项式求逆，一次NTT
void sqr(int *f,int *g,int n){ if(n==1){ g[0]=1;return; } sqr(f,g,n>>1); for(reg i=0;i<n/2;++i) co[i]=(ll)g[i]%mod,l[i]=g[i],p[i]=f[i],ni[i]=0; for(reg i=n/2;i<n;++i) co[i]=0,l[i]=0,p[i]=f[i],ni[i]=0; for(reg i=n;i<2*n;++i) co[i]=0,l[i]=0,p[i]=0,ni[i]=0; memset(ni,0,sizeof ni); inv(co,ni,n); calc(p,ni,2*n); for(reg i=0;i<2*n;++i){ if(i<n) g[i]=((ll)g[i]+p[i])%mod*inv2%mod; else g[i]=0; } }
例题：小朋友和二叉树
听说可以用ln和exp代替（但是常数很大）？
先学了ln和exp再说
原文：https://www.cnblogs.com/Miracevin/p/10332070.html