多项式 ln

定义

\(给一多项式F(x),求G(x)\equiv lnF(x)\pmod x^n\)

前置知识

\(不定积分\)

\(微分\)

\(多项式乘法逆\)

推式子：

\[\because G(x)\equiv lnF(x)\pmod x^n
\]

\[又\because lnF(x)=\int dlnF(x)
\]

\[=\int (lnF(x))'dx
\]

\[=\int \frac{F'(x)}{F(x)}dx
\]

步骤：

\(1.求F(x)的导数\)

\(2.求F(x)的逆F_r(x)\)

\(3.求\int F(x)F_r(x)dx\)

\[\\
\]

【模板】多项式对数函数（多项式 ln）

\[\\
\]

\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)

#include<cstdio>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

# define read read1<int>()

# define Type template<typename T>

Type inline T read1(){

    T n=0;

    char k;

    bool fl=0;

    do (k=getchar())=='-'&&(fl=1);while('9'<k||k<'0');

    while(47<k&&k<58)n=(n<<3)+(n<<1)+(k^48),k=getchar();

    return fl?-n:n;

}

# define f(i,l,r) for(int i=(l);i<=(r);++i)

# define fre(k) freopen(k".in","r",stdin);freopen(k".ans","w",stdout)

# define ll int64_t

class Array{

    private:

        vector<int>a;

    public:

        Array(const int size,const int f):a(size,f){}

        void push(int n){a.push_back(n);}

        Array(int* l=NULL,int* r=NULL){while(l!=r)push(*l),++l;}

        inline int size(){return a.size();}

        inline int& operator [] (const int x){return a[x];}

        void resize(int n){a.resize(n);}

        void clear(){a.clear();}

        void swap(){reverse(a.begin(),a.end());}

        int& top(){return a[a.size()-1];}

        void pop(){a.pop_back();}

};

const int mod=998244353,g=3,inv2=499122177;

Array operator -(Array a,Array b){

    int N=a.size(),M=b.size();

    Array t;

    for(int i=0;i<N&&i<M;++i){

        t.push((i<N?a[i]:0)-(i<M?b[i]:0));

        if(t.top()<0)t.top()+=mod;

    }

    return t;

}

Array operator +(Array a,Array b){

    int N=a.size(),M=b.size();

    Array t;

    for(int i=0;i<N&&i<M;++i){

        t.push((i<N?a[i]:0)+(i<M?b[i]:0));

        if(t.top()>=mod)t.top()-=mod;

    }

    return t;

}

Array operator *(Array a,int n){

    int N=a.size();

    for(int i=0;i<N;a[i]=(ll)a[i]*n%mod,++i);

    return a;

}

Array operator *(int n,Array a){return a*n;}

int qkpow(int b,int m,int mod){

    int tem=b,ans=1;

    for(;m;m>>=1,tem=(ll)tem*tem%mod)

        if(m&1)ans=(ll)ans*tem%mod;

    return ans;

}

int* NTT(const int len,Array& a,const bool Ty,int* r=NULL){

    if(!r){

        r=new int[len];

        r[0]=0;int L=log2(len);

        f(i,0,len-1)

            r[i]=(r[i>>1]>>1)|((i&1)<<L-1);

    }

    f(i,0,len-1)

        if(i<r[i])swap(a[i],a[r[i]]);

    for(int i=1;i<len;i<<=1){

        int T=qkpow(Ty?g:332748118,(mod-1)/(i<<1),mod);

        for(int W=i<<1,j=0;j<len;j+=W){

            ll omega=1;

            for(int k=0;k<i;++k,omega=omega*T%mod){

                ll x(a[j+k]),y(omega*a[i+j+k]%mod);

                a[j+k]=x+y;(a[j+k]>mod)&&(a[j+k]-=mod);

                a[i+j+k]=x-y+mod;(a[i+j+k]>mod)&&(a[i+j+k]-=mod);

            }

        }

    }

    return r;

}

Array operator * (Array x,Array y){

    int n=x.size()-1,m=y.size()-1;

    int limit=1;

    while(limit<=n+m)limit<<=1;

    Array ans;

    x.resize(limit+1);

    y.resize(limit+1);

    int *r;

    r=NTT(limit,x,1);

    NTT(limit,y,1,r);

    f(i,0,limit)x[i]=(ll)x[i]*y[i]%mod;

    NTT(limit,x,0,r);

    int tem=qkpow(limit,mod-2,mod);

    f(i,0,n+m)ans.push((ll)x[i]*tem%mod);

    return ans;

}

Array& operator *= (Array& x,Array y){

    return x=x*y;

}

void Rev(Array &x,Array y){

    int n=x.size()-1,m=y.size()-1;

    int limit=1;

    while(limit<=n+m)limit<<=1;

    Array ans;

    x.resize(limit+1);

    y.resize(limit+1);

    int *r;

    r=NTT(limit,x,1);

    NTT(limit,y,1,r);

    f(i,0,limit)x[i]=(ll)(2ll-(ll)x[i]*y[i]%mod+mod)%mod*y[i]%mod;

    NTT(limit,x,0,r);

    int tem=qkpow(limit,mod-2,mod);

    f(i,0,n+m)x[i]=(ll)x[i]*tem%mod;

    x.resize(n+m+1);

}

Array Inv(Array a){

    int N=a.size();

    // printf("%d\n",N);

    if(N==1)return Array(1,qkpow(a[0],mod-2,mod));

    Array b=a;b.resize(N+1>>1);

    b=Inv(b);b.resize(N);

    Rev(a,b);

    a.resize(N);

    return a;

}

Array operator / (Array x,Array y){

    int N=x.size()-1,M=y.size()-1;

    if(N<M)return Array(1,0);

    x.swap();y.swap();

    y.resize(N-M+1);

    x*=Inv(y);

    x.resize(N-M+1);

    x.swap();

    return x;

}

Array sqrt(Array x){

    int N=x.size();

    if(N==1)return Array(1,1);

    Array y=x;

    y.resize(N+1>>1);

    y=sqrt(y);

    y.resize(N);

    Array z=Inv(y);

    return inv2*(y+x*z);

}

Array diff(Array x){

    for(int i=0;i+1<x.size();++i)

        x[i]=(ll)x[i+1]*(i+1)%mod;

    x.pop();

    return x;

}

Array integral(Array x){

    for(int i=x.size();--i;)

        x[i]=(ll)x[i-1]*qkpow(i,mod-2,mod)%mod;

    x[0]=0;

    return x;

}

Array ln(Array x){

    int N=x.size();

    x=integral(diff(x)*Inv(x));

    x.resize(N);

    return x;

}

int n;

Array x;

int main(){

    n=read;

    for(int i=0;i<n;++i)x.push(read);

    x=ln(x);

    for(int i=0;i<n;++i)printf("%d ",x[i]);

    return 0;

}

巴特西

多项式 ln

多项式 ln

定义

前置知识

推式子：

步骤：

最新文章

热门文章