Loading...

洛谷P4725 多项式对数函数

check评论:0 条 remove_red_eye浏览量:330 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-23

给定多项式$A(x)$,求多项式$G(x)$使得$$G(x)\equiv lnA(x) \pmod {998244353}$$

设$F(x)=ln(x)$,则$G(x)=F(A(x))$,求导后$G'(x)=F'(A(x))A'(x)=\frac{A'(x)}{A(x)}$

然后对$A(x)$求导,乘上其逆元,再不定积分就好,已经规定了常数项为$0$

$\int x^adx=\frac{x^{a+1}}{a+1}$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353,ge=3;
ll a[800010],b[800010],c[800010];
int r[800010],n;
ll ksm(ll qaq,int f)
{
    ll res=1;
    while(f)
    {
        if(f&1)
        {
            res=res*qaq%mod;
        }
        qaq=qaq*qaq%mod;
        f>>=1;
    }
    return res;
}
void NTT(ll *x,int len,int flag)
{
    for(int i=0;i<len;i++)
    {
        if(i<r[i])
        {
            swap(x[i],x[r[i]]);
        }
    }
    for(int mid=1;mid<len;mid<<=1)
    {
        ll wn=ksm(ge,flag==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)));
        for(int r=(mid<<1),i=0;i<len;i+=r)
        {
            ll w=1;
            for(int k=0;k<mid;k++,w=w*wn%mod)
            {
                ll m1=x[i+k],m2=w*x[i+mid+k]%mod;
                x[i+k]=(m1+m2)%mod,x[i+mid+k]=(m1-m2+mod)%mod;
            }
        }
    }
}
void work(int len,ll *a,ll *b)
{
    if(len==1)
    {
        b[0]=ksm(a[0],mod-2);
        return ;
    }
    work((len+1)>>1,a,b);
    int lim=1,l=0;
    while(lim<(len<<1))
    {
        lim<<=1,l++;
    }
    for(int i=1;i<lim;i++)
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    for(int i=0;i<len;i++)
    {
        c[i]=a[i];
    }
    for(int i=len;i<lim;i++)
    {
        c[i]=0;
    }
    NTT(c,lim,1),NTT(b,lim,1);
    for(int i=0;i<lim;i++)
    {
        b[i]=(2LL-c[i]*b[i]%mod+mod)%mod*b[i]%mod;
    }
    NTT(b,lim,-1);
    ll ny=ksm(lim,mod-2);
    for(int i=0;i<lim;i++)
    {
        b[i]=b[i]*ny%mod;
    }
    for(int i=len;i<lim;i++)
    {
        b[i]=0;
    }
}
void dao(ll *a)
{
    for(int i=0;i<n-1;i++) 
    {
        a[i]=a[i+1]*(i+1)%mod;
    } 
    a[n-1]=0;
}
void gint(ll *a)
{
    for(int i=n-1;i>=1;i--) 
    {
        a[i]=a[i-1]*ksm(i,mod-2)%mod;
    } 
    a[0]=0; 
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) 
    {
        scanf("%lld",&a[i]);
    }
    work(n,a,b);
    dao(a);
    int lim=1,l=0;
    while(lim<(n<<1)+2) 
    {
        lim<<=1,l++;
    }
    for(int i=1;i<lim;i++) 
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    NTT(a,lim,1),NTT(b,lim,1);
    for(int i=0;i<=lim;i++) 
    {
        b[i]=(b[i]*a[i])%mod;
    }
    NTT(b,lim,-1);
    ll ny=ksm(lim,mod-2);
    for(int i=0;i<lim;i++) 
    {
        b[i]=b[i]*ny%mod;
    }
    gint(b);
    for(int i=0;i<n;i++) 
    {
        printf("%lld ",b[i]);
    }
}

序列统计 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名