给出 \(n-1\) 次多项式 \(F(x)\),求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\),满足 \(g(x) \equiv \ln f(x)\)(\(f_0=1\))。
\[g'(x)=\ln'(f(x))\times f'(x)=\frac{f'(x)}{f(x)}(\bmod x^n) \]求导,求逆,求积即可。
LL Tmp[N];
void PolyInv(LL*a,LL*I,LL n){
if(n==1){I[0]=ksm(a[0]);return;}
int m=n+1>>1;PolyInv(a,I,m);
Mul(I,I,Tmp,m,m,n),Mul(Tmp,a,Tmp,n,n,n);
for(int i=0;i<n;i++)I[i]=(2ll*I[i]-Tmp[i]+mo)%mo;
}
void PolyQd(LL*a,LL*b,LL n){for(int i=0;i<n-1;i++)b[i]=a[i+1]*(i+1)%mo;b[n-1]=0;}
void PolyQj(LL*a,LL*b,LL n){for(int i=n-1;i>0;i--)b[i]=a[i-1]*ksm(i)%mo;b[0]=0;}
LL TMP[N];
void PolyLn(LL*a,LL*ln,LL n){
PolyInv(a,TMP,n);PolyQd(a,ln,n);
Mul(ln,TMP,TMP,n,n,n);PolyQj(TMP,ln,n);
}
int n; LL a[N],Ln[N];
标签:Tmp,TMP,ln,多项式,LL,int
From: https://www.cnblogs.com/dadidididi/p/17692280.html