【模板】多项式指数函数（多项式 exp）题解

Illusory_dimes · 2021-03-31 18:25:26 · 题解

题目大意

给定 n-1 次多项式 g(x) ，求多项式 f(x) 满足：

f(x)\equiv\exp^{g(x)}$ $(mod$ $x^n)

系数对 998244353 取模。

数据范围 n\leq 10^5 。

前置芝士：

多项式 \ln ，~~非常入门的~~求导，积分和恶俗的牛顿迭代。

第一个不会出门左拐，最后两个的话，这里只要：

求导公式 \mathrm{d} x^{a}=ax^{a-1} 。

求导法则 \mathrm{d} f[g(x)]=f^{'}[g(x)]\cdot g^{'}(x) 。

积分公式 \int x^a=\frac{1}{a+1}x^{a+1} 。

牛顿迭代的话，珂以看看我的文章（虽然不咋地。。），大概了解一下原理就好

solution

对于多项式刚刚杠到这题的我们来说， \exp 实在有点陌生，但 \ln 肯定已经见过了。

所以聪明的你一定注意到了 \exp^{g(x)} 取 \ln 后 \Longrightarrow g(x) 。

漂亮，

f(x)\equiv\exp^{g(x)}$ $(mod$ $x^n)

两边同时取个 \ln ：

\ln_{}{f(x)}\equiv g(x)$ $(mod$ $x^n)

设 \varphi(f(x))=\ln_{}{f(x)}-g(x)\equiv0 (mod x^n)

用一下上面提到的牛顿迭代的公式

f(x)\equiv f_0(x)-\Large\frac{\ln f_0(x)-g(x)}{\frac{1}{f_0(x)}}

化简一下：

f(x)\equiv f_0(x)\cdot(1+g(x)-\ln f_0(x))

完了，

用一下 \ln 的求法就行了

时间复杂度 O(n\log_{2}{n}) 。

人傻常熟大 wtcl 。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+10;
typedef ll arr[N];
const int mod=998244353;
const int inv3=332748118;
int n,inv,lim=1,fre,id[N];
arr f,g,ans,tmp,ln;
inline ll inc(ll x,ll y){return x+y>=mod?x+y-mod:x+y;}
inline ll dec(ll x,ll y){return x-y<0?x-y+mod:x-y;}
inline ll mul(ll x,ll y){return 1ll*x*y%mod;}
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline int ksm(int a,int b)
{
    int tmp=1;
    while(b)
    {
        if(b&1)tmp=(1ll*tmp*a)%mod;
        b>>=1,a=(1ll*a*a)%mod;
    }
    return tmp;
}
inline void Never_Tell_TLE(ll* NTT,int sign)
{
    for(int i=0;i<=lim;++i)if(i<id[i])
    {
        ll NTt=NTT[i];
        NTT[i]=NTT[id[i]];
        NTT[id[i]]=NTt;
    }
    for(int mid=1;mid<lim;mid<<=1)
    {
        int Unit_root;
        if(sign==1)Unit_root=ksm(3,(mod-1)/(mid<<1));
        else Unit_root=ksm(inv3,(mod-1)/(mid<<1));
        for(int R=mid<<1,r=0;r<lim;r+=R)
        {
            int pw=1;
            for(int l=0;l<mid;++l,pw=(1ll*pw*Unit_root)%mod)
            {
                int butt=NTT[l+r],rfly=(1ll*pw*NTT[l+r+mid])%mod;
                NTT[l+r]=inc(butt,rfly);
                NTT[l+r+mid]=dec(butt,rfly);
            }
        }
    }
    if(sign==-1)
    {
        int inv_lim=ksm(lim,mod-2);
        for(int i=0;i<=lim;++i)NTT[i]=(1ll*NTT[i]*inv_lim)%mod;
    }
}
inline void Derivation(ll* F,ll* G,int nm)
{
    for(int i=1;i<nm;++i)
    G[i-1]=mul(1ll*i,F[i]);
    G[nm-1]=0;
}
inline void Inv(ll* F,ll* G,int nm)
{
    if(nm==1)
    {
        G[0]=ksm(F[0],mod-2);
        return;
    }
    Inv(F,G,(nm+1)>>1);
    lim=1,fre=0;
    for(;lim<(nm<<1);lim<<=1)++fre;
    for(int i=0;i<=lim;++i)id[i]=(id[i>>1]>>1)|((i&1)<<(fre-1));
    for(int i=0;i<nm;++i)ans[i]=F[i];
    for(int i=nm;i<=lim;++i)ans[i]=0;
    Never_Tell_TLE(ans,1),Never_Tell_TLE(G,1);
    for(int i=0;i<=lim;++i)G[i]=mul(inc(2ll,-mul(ans[i],G[i])+mod),G[i]);
    Never_Tell_TLE(G,-1);
    for(int i=nm;i<=lim;++i)G[i]=0;
}
inline void Mul(ll* F,ll* G,int nm)
{
    lim=1,fre=0;
    for(;lim<(nm<<1);lim<<=1)++fre;
    for(int i=0;i<=lim;++i)id[i]=(id[i>>1]>>1)|((i&1)<<(fre-1));
    int inv_lim=ksm(lim,mod-2);
    Never_Tell_TLE(G,1),Never_Tell_TLE(F,1);
    for(int i=0;i<=lim;++i)G[i]=mul(F[i],G[i]);
    Never_Tell_TLE(G,-1);
}
inline void Integral(ll* F,ll* G,int nm)
{
    for(int i=1;i<nm;++i)
    G[i]=mul(F[i-1],ksm(i,mod-2));
    G[0]=0;
}
inline void Ln(ll* F,ll* G,int nm)
{
    Inv(F,tmp,nm);
    for(int i=0;i<=lim;++i)ans[i]=0;
    Derivation(F,ans,nm);
    Mul(tmp,ans,nm);
    Integral(ans,G,nm);
    for(int i=0;i<=lim;++i)ans[i]=tmp[i]=0;
}
inline void solve(ll* F,ll* G,int nm)
{
    if(nm==1)
    {
        G[0]=1;
        return;
    }
    solve(F,G,(nm+1)>>1);
    lim=1,fre=0;
    for(;lim<(nm<<1);lim<<=1)++fre;
    for(int i=0;i<=lim;++i)id[i]=(id[i>>1]>>1)|((i&1)<<(fre-1));
    for(int i=0;i<=lim;++i)ln[i]=0;
    Ln(G,ln,nm);
    for(int i=0;i<nm;++i)ans[i]=F[i];
    for(int i=nm;i<=lim;++i)ans[i]=0;
    Never_Tell_TLE(ans,1),Never_Tell_TLE(G,1),Never_Tell_TLE(ln,1);
    for(int i=0;i<=lim;++i)G[i]=mul(inc(1ll,inc(ans[i],-ln[i]+mod)),G[i]);
    Never_Tell_TLE(G,-1);
    for(int i=nm;i<=lim;++i)G[i]=0;
}
int main()
{
    n=read();
    for(int i=0;i<n;++i)f[i]=read();
    solve(f,g,n);
    for(int i=0;i<n;++i)printf("%d ",g[i]);
    return 0;
}

只求能帮助到几个人罢。。

【模板】多项式指数函数（多项式 exp） 题解

题目大意

前置芝士：

solution

【模板】多项式指数函数（多项式 exp）题解