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

发表于 |
字数统计: 1k | 阅读时长 ≈ 5

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

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

链接

Luogu P4725

题解

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

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

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#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]);
    }
}