题目概述

求 $B(x)=lnA(x)(mod\ x^n)$ ，即满足 $A(x)=e^{B(x)}$ 。

解题报告

前置姿势：多项式求逆，多项式求导，多项式积分。

• 多项式求导：就是对每项分别求导：$(a_ix_i)'=ia_ix^{i-1},F'(x)=\sum_{i=0}^{n}if_ix^{i-1}$ 。
• 多项式积分：求导的逆过程：$\int(a_ix^i)={a_i\over i+1}x^{i+1},\int F(x)=\sum_{i=0}^{n}{f_i\over i+1}x^{i+1}$ 。

那么我们对式子两边求导，可以得到：$B'(x)={A'(x)\over A(x)}$ 。直接多项式求逆，求导，积分就行了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=262144,MOD=998244353;

int n,a[maxn+5],b[maxn+5],rev[maxn+5],pw[2][maxn+5],tem[maxn+5];

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
void Inv(int *a,int *b,int n){
    if (n==1) {b[0]=Pow(a[0],MOD-2);return;}Inv(a,b,n>>1);Pre(n<<1);
    for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=b[i+n]=0;NTT(tem,n<<1,1);NTT(b,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=(LL)b[i]*(2+MOD-(LL)b[i]*tem[i]%MOD)%MOD;
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) b[i]=tem[i],b[i+n]=0;
}
inline void Ln(int *a,int *b,int n){
    static int A[maxn+5],B[maxn+5];for (int i=0;i<n;i++) A[i]=(LL)(i+1)*a[i+1]%MOD,A[i+n]=0;Inv(a,B,n);
    Pre(n<<1);NTT(A,n<<1,1);NTT(B,n<<1,1);for (int i=0;i<(n<<1);i++) B[i]=(LL)A[i]*B[i]%MOD;
    NTT(B,n<<1,-1);for (int i=1;i<n;i++) b[i]=(LL)B[i-1]*Pow(i,MOD-2)%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=0;i<n;i++) scanf("%d",&a[i]);int t;for (t=1;t<n;t<<=1);Ln(a,b,t);
    for (int i=0;i<n;i++) i?putchar(' '):0,printf("%d",b[i]);puts("");return 0;
}