多项式$\exp$学习笔记

已知$n-1$次多项式$A(x)$,求$B(x)$满足$$B(x)\equiv e^{A(x)}\pmod{x^{n}}$$

我们可以考虑一下牛顿迭代w

设$$F(x)=\ln x-A(x)$$
则有$$F(B(x))\equiv 0\pmod{x^n}$$
带入牛顿迭代的式子得$$\begin{split}
B_{t+1}(x)&\equiv B_t(x)-\frac{F(B_t(x))}{F'(B_t(x))}\\
&\equiv B_t(x)- B_t(x)\cdot (\ln B_t(x)-A(x))\\
&\equiv B_t(x)\cdot (1-\ln{B_t(x)+A(x)}) \pmod{x^n}
\end{split}$$

#include <iostream>
#include <cstdio>
#include <cstring>

template <typename T> void in(T &_){
    char _c=getchar(); int fl=1; _=0;
    while(!isdigit(_c)) fl=_c=='-'?-1:fl, _c=getchar();
    while(isdigit(_c)) _=_*10+_c-'0', _c=getchar(); _*=fl;
}

const int MOD=998244353, G=3, iG=332748118;

int ksm(int x, int y){
    int z=1;
    for(; y; x=1LL*x*x%MOD, y>>=1) if(y&1) z=1LL*z*x%MOD;
    return z;
}

namespace Poly{
    int rev[400010], C[400010], D[400010], E[400010];

    void get_rev(int l){
        for(int i=0; i<l; i++) 
            rev[i]=(rev[i>>1]>>1)|((i&1) ? l>>1 : 0);
    }

    void ntt(int *P, int l, int opt){
        for(int i=0; i<l; i++) if(i>rev[i]) 
            std::swap(P[i], P[rev[i]]);
        for(int i=1; i<l; i<<=1){
            int W=opt>0 ? G : iG;
            W=ksm(W, (MOD-1)/(2*i));
            for(int j=0, p=2*i; j<l; j+=p)
                for(int k=0, w=1; k<i; k++, w=1LL*w*W%MOD){
                    int X=P[j+k], Y=1LL*P[i+j+k]*w%MOD;
                    P[j+k]=(X+Y)%MOD, P[i+j+k]=(X-Y)%MOD;
                }
        }
        if(opt>0) return; int inv=ksm(l, MOD-2);
        for(int i=0; i<l; i++) P[i]=1LL*P[i]*inv%MOD;
    }

    void Inv(int *A, int *B, int n){
        if(n==1){B[0]=ksm(A[0], MOD-2); return;}
        Inv(A, B, (n+1)/2);
        int l=1; while(l<(2*n)) l<<=1;
        for(int i=0; i<n; i++) C[i]=A[i];
        for(int i=n; i<l; i++) C[i]=0;
        get_rev(l);
        ntt(B, l, 1); ntt(C, l, 1);
        for(int i=0; i<l; i++) B[i]=1LL*B[i]*(2LL-1LL*C[i]*B[i]%MOD)%MOD;
        ntt(B, l, -1);
        for(int i=n; i<l; i++) B[i]=0;
    }

    void Dev(int *P, int l){
        for(int i=1; i<l; i++) P[i-1]=1LL*i*P[i]%MOD; P[l]=0;
    }

    void Int(int *P, int l){
        for(int i=l-1; i; i--) P[i]=1LL*ksm(i, MOD-2)*P[i-1]%MOD; P[0]=0;
    }

    void Ln(int *A, int *B, int n){
        for(int i=0; i<n; i++) D[i]=A[i];
        int l=1; while(l<2*n) l<<=1;
        for(int i=0; i<l; i++) B[i]=0;
        Inv(A, B, n); Dev(D, n);
        for(int i=n; i<l; i++) D[i]=0, B[i]=0;
        get_rev(l); ntt(D, l, 1); ntt(B, l, 1);
        for(int i=0; i<l; i++) B[i]=1LL*B[i]*D[i]%MOD;
        ntt(B, l, -1); for(int i=n; i<l; i++) B[i]=0;
        Int(B, n);
    }

    void Exp(int *A, int *B, int n){
        if(n==1){B[0]=1; return;}
        Exp(A, B, (n+1)/2);
        Ln(B, E, n);
        int l=1; while(l<2*n) l<<=1;
        get_rev(l);
        E[0]=(1-E[0]+A[0])%MOD;
        for(int i=1; i<n; i++) E[i]=(A[i]-E[i])%MOD;
        for(int i=n; i<l; i++) E[i]=0;
        ntt(B, l, 1); ntt(E, l, 1);
        for(int i=0; i<l; i++) B[i]=1LL*B[i]*E[i]%MOD;
        ntt(B, l, -1);
        for(int i=n; i<l; i++) B[i]=0;
    }
}

int n, A[400010], B[400010];

int main(){
    in(n);
    for(int i=0; i<n; i++) in(A[i]);
    Poly::Exp(A, B, n);
    for(int i=0; i<n; i++) printf("%d ", (B[i]+MOD)%MOD);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注