「Luogu P4725」【模板】多项式对数函数

给定一个$n-1$次整系数多项式$F(x)$，求在$\bmod x^n$意义下的整系数多项式$G(x)$，使得$G(x)=\ln F(x)$。

在$\bmod 998244353$下进行，且$F(x)$系数均在$[0,998244352]$范围内。

链接

Luogu P4725

题解

首先声明，这题要使用微积分知识。（不会的可以看我的微积分初步的笔记（一个大坑））

自然对数直接求感觉很不对劲，但是有这样一个好东西：

$$\cfrac{\mathrm{d}}{\mathrm{d}x}\ln x=\cfrac{1}{x}$$

所以说可以考虑将等式两边求导，右边用链式求导法则搞一下，会得到这个

$$G^\prime(x)=\cfrac{F^\prime(x)}{F(x)}$$

右边很明显，是$F(x)$的逆乘上它的导数，使用多项式求导和求逆即可算出右边。左边是$G(x)$的导数，而右边是可以求出的多项式，所以可以对右边在膜意义下求不定积分求出$G(x)$，即

$$G(x)=\int \cfrac{F^\prime(x)}{F(x)}$$

时间复杂度当然只有多项式求逆的$O(n\log n)$啦qwq

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MAXN=3e5+51,MOD=998244353,G=3;
ll fd,gd;
ll f[MAXN],res[MAXN],tmp[MAXN],pinv[MAXN],der[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll qadd(ll x,ll y,ll mod)
{
    return x+y>mod?x+y-mod:x+y;
}
inline ll qmin(ll x,ll y,ll mod)
{
    return x-y<0?x-y+mod:x-y;
}
inline ll qpow(ll base,ll exponent,ll mod)
{
    if(!exponent)
    {
        return 1;
    }
    ll temp=qpow(base,exponent>>1,mod),res=temp*temp%mod;
    if(exponent&1)
    {
        res=res*base%mod;
    }
    return res;
}
inline void NTT(ll *cp,ll cnt,ll inv,ll mod)
{
    ll lim=0,cur=0,res=0,omg=0;
    while((1<<lim)<cnt)
    {
    	lim++;
    }
    for(register int i=0;i<cnt;i++)
    {
        cur=0;
        for(register int j=0;j<lim;j++)
        {
            if((i>>j)&1)
            {
                cur|=(1<<(lim-j-1));
            }
        }
        if(i<cur)
        {
            swap(cp[i],cp[cur]);
        }
    }
    for(register int i=2;i<=cnt;i<<=1)
    {
        cur=i>>1,res=qpow(G,(mod-1)/i,mod);
        for(register ll *p=cp;p!=cp+cnt;p+=i)
        {
            omg=1;
            for(register int j=0;j<cur;j++)
            {
                ll t=omg*p[j+cur]%mod;
                p[j+cur]=qmin(p[j],t,mod);
                p[j]=qadd(p[j],t,mod);
                omg=omg*res%mod;
            }
        }
    }
    if(inv==-1)
    {
        ll invl=qpow(cnt,mod-2,mod);
        cp[0]=cp[0]*invl%mod;
        for(register int i=1;i<=cnt>>1;i++)
        {
            cp[i]=cp[i]*invl%mod;
            if(i!=cnt-i)
            {
                cp[cnt-i]=cp[cnt-i]*invl%mod;
            }
            swap(cp[i],cp[cnt-i]);
        }
    }
}
inline void deriv(ll fd,ll *f,ll *res,ll mod)
{
    for(register int i=1;i<fd;i++)
    {
        res[i-1]=f[i]*i%mod;
    }
    res[fd-1]=0;
}
inline void integ(ll fd,ll *f,ll *res,ll mod)
{
    for(register int i=1;i<fd;i++)
    {
        res[i]=f[i-1]*qpow(i,mod-2,mod)%mod;
    }
    res[0]=0;
}
inline void inv(ll fd,ll *f,ll *res,ll mod)
{
    if(fd==1)
    {
        res[0]=qpow(f[0],mod-2,mod);
        return;
    }
    inv((fd+1)>>1,f,res,mod);
    ll cnt=1;
    while(cnt<(fd<<1))
    {
        cnt<<=1;
    }
    for(register int i=0;i<cnt;i++)
    {
        tmp[i]=i<fd?f[i]:0;
    }
    NTT(tmp,cnt,1,mod),NTT(res,cnt,1,mod);
    for(register int i=0;i<cnt;i++)
    {
        res[i]=qmin(2,tmp[i]*res[i]%mod,mod)*res[i]%mod;
    }
    NTT(res,cnt,-1,mod);
    for(register int i=fd;i<cnt;i++)
    {
        res[i]=0;
    }
}
inline void ln(ll fd,ll *f,ll *res,ll mod)
{
    ll cnt=1;
    while(cnt<(fd<<1))
    {
        cnt<<=1;
    }
    inv(fd,f,pinv,mod),deriv(fd,f,der,mod);
    NTT(pinv,cnt,1,mod),NTT(der,cnt,1,mod);
    for(register int i=0;i<cnt;i++)
    {
        der[i]=der[i]*pinv[i]%mod;
    }
    NTT(der,cnt,-1,mod),integ(fd,der,res,mod);
    for(register int i=0;i<cnt;i++)
    {
        der[i]=pinv[i]=0;
    }
}
int main()
{
    fd=read();
    for(register int i=0;i<fd;i++)
    {
        f[i]=read();
    }
    ln(fd,f,res,MOD);
    for(register int i=0;i<fd;i++)
    {
        printf("%lld ",res[i]);
    }
}