题目概述

求 $B(x)=e^{A(x)}\ mod\ x^n$ 。

解题报告

前置姿势：多项式求逆，多项式ln。

第一种方法是两边求导：

$$ B'(x)=e^{A(x)}A'(x)\\ B'(x)=B(x)A'(x)\\ (i+1)b_{i+1}=\sum_{j=0}^{i}b_{i-j}(j+1)a_{j+1}\\ (i+1)b_{i+1}=\sum_{j=1}^{i+1}jb_{i-j}a_j\\ b_i={1\over i}\sum_{j=1}^{i}jb_{i-j}a_j $$

然后使用分治FFT，复杂度 $O(nlog_2^2n)$ 。

第二种方法是牛顿迭代：设 $F(x)$ 为待求多项式，令多项式 $G(x)$ 满足 $G(F(x))=0$ ，如果我们已经求出 $mod\ x^n$ 下的 $F_0(x)$ ，那么将 $G(F(x))$ 在 $F_0(x)$ 处进行泰勒展开：

$$ G(F(x))=G(F_0(x))+G'(F_0(x))[F(x)-F_0(x)]+{G''(F_0(x))[F(x)-F_0(x)]^2\over 2!}+\cdots=0\\ $$

由于 $F(x)\equiv F_0(x)(mod\ x^n)\Rightarrow[F(x)-F_0(x)]^2\equiv0(mod\ x^{2n})$ ，所以：

$$ G(F_0(x))+G'(F_0(x))[F(x)-F_0(x)]\equiv0(mod\ x^{2n})\\ F(x)\equiv F_0(x)-{G(F_0(x))\over G'(F_0(x))}(mod\ x^{2n}) $$

只需要知道 $F(x)$ 的常数项并且构造出 $G(F(x))$ ，就可以倍增求出 $F(x)$ 啦！

对于 $F(x)=e^{A(x)}$ ，我们可以构造 $G(F(x))=ln(F(x))-A(x)=0$ ，代入上面的式子：

$$ F(x)\equiv F_0(x)-{ln(F_0(x))-A(x)\over{1\over F_0(x)}}\equiv F_0(x)[1-ln(F_0(x))+A(x)](mod\ x^{2n}) $$

由于保证了 $a_0=0$ ，所以 $f_0=1​$ 。用多项式ln就行了。

示例程序

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

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

inline void Make(int n) {INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;}
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)tem[i]*b[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);b[0]=0;for (int i=1;i<n;i++) b[i]=(LL)INV[i]*B[i-1]%MOD;
}
void Exp(int *a,int *b,int n){
    if (n==1) {b[0]=1;return;}Exp(a,b,n>>1);Ln(b,tem,n);Pre(n<<1);
    for (int i=0;i<n;i++) tem[i]=(a[i]+MOD-tem[i])%MOD,tem[i+n]=b[i+n]=0;AMOD(tem[0],1);
    NTT(tem,n<<1,1);NTT(b,n<<1,1);for (int i=0;i<(n<<1);i++) tem[i]=(LL)tem[i]*b[i]%MOD;
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) b[i]=tem[i],b[i+n]=0;
}
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);Make(t);
    Exp(a,b,t);for (int i=0;i<n;i++) i?putchar(' '):0,printf("%d",b[i]);puts("");return 0;
}