多项式 $\ln$ 学习笔记

Luogu P4725

$$\begin{split}
B(x)&\equiv\ln A(x)\\
B'(x)&\equiv\frac{A'(x) }{A(x)}\\
B(x)&\equiv \int \frac{A'(x)}{A(x)}\text{d}x
\end{split}$$

$$\begin{split}
A(x)&=\sum \limits_{i=0}^{n}a_ix^i\\
A'(x)&=\sum \limits_{i=1}^{n}ia_ix^{i-1}\\
\int A(x)\text{d}x&=\sum\limits_{i=0}^n\frac{a_ix^{i+1}}{i+1}
\end{split}$$

#include <iostream>
#include <cstdio>

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

const int MOD=998244353, G=3, iG=332748118;
int N, A[400010], invA[400010], rev[400010], c[400010];

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

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(rev[i]>i) std::swap(P[i], P[rev[i]]);
    for(int i=1; i<l; i<<=1){
        int W=ksm(opt>0 ? G : iG, (MOD-1)/(2*i));
        for(int p=2*i, j=0; j<l; j+=p)
            for(int w=1, k=0; k<i; k++, w=1LL*w*W%MOD){
                int X=P[j+k], Y=1LL*w*P[i+j+k]%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 get_inv(int *a, int *b, int n){
    if(n==1){b[0]=a[0]; return;}
    get_inv(a, b, (n+1)/2);
    int l=1; while(l<2*n) l<<=1;
    get_rev(l);
    for(int i=0; i<n; i++) c[i]=a[i];
    for(int i=n; i<l; i++) c[i]=0;
    ntt(c, l, 1); ntt(b, l, 1);
    for(int i=0; i<l; i++) b[i]=(2LL-1LL*c[i]*b[i]%MOD)*b[i]%MOD;
    ntt(b, l, -1);
    for(int i=n; i<l; i++) b[i]=0;
}

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

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

int main(){
    in(N);
    for(int i=0; i<N; i++) in(A[i]);
    get_inv(A, invA, N);
    get_derivative(A, N);
    int l=1; while(l<2*N) l<<=1;
    get_rev(l);
    ntt(A, l, 1); ntt(invA, l, 1);
    for(int i=0; i<l; i++) A[i]=1LL*A[i]*invA[i]%MOD;
    ntt(A, l, -1);
    get_integral(A, N);
    for(int i=0; i<N; i++) printf("%d ", (A[i]+MOD)%MOD);
    return 0;
}

发表评论

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