对数ln

对数ln

-家庭报告

2023年2月15日发(作者：蛙跳)

多项式对数函数（多项式ln）

前置知识

ln求导

求ln

′(t)。

结论

ln′(t)=

1

t

证明

设：

1

ε

ln(1+

ε

t

)=k

1

kε

ln(1+

ε

t

)=1

(1+

ε

t

)

1

kε=e=

lim

x→∞(1+

1

x

)

x

那么就得到了：

ε

t

=

1

x

1

kε

=x

相乘得到：

1

kt

=1

那么：

k=

1

t

ln′(t)=

1

t

⾄此，证毕。

多项式求导

求f

′(x)。

结论

[x

t

]f(x)⋅x

t

→t⋅[x

t

]f(x)⋅x

t−1

写得和蔼⼀点就是：a

i

⋅x

i

→a

i

⋅i⋅x

i−1

积分同理，即回带。

证明

稍微咕⼀下，就⼀下。

复合函数求导法则

结论

h(x)=f[g(x)],h′(x)=f′[g(x)]⋅g′(x)

证明

稍微咕⼀下，就

多项式求ln

求ln(f(x))=g(x)。

g′(x)=ln′(f(x))⋅f′(x)=

1

f(x)

⋅f′(x)

正题

由前⾯我们已经发现了ln函数的优美性质，其导数为

1

x

。

{

Loading[MathJax]/extensions/TeX/

结合复合函数求导公式，我们就可以⼲⼀些好玩的事情。

对于：

lnA(x)equivB(x)pmodp

我们就可以通过复合函数求导得到：

ln'A(x)cdotA'(x)equivB'(x)

frac{1}{A(x)}cdotA'(x)equivB'(x)

对于给定的A，第⼀项，我们可以由求逆得到，第⼆项，由多项式求导得到。

于是我们就可以将两者卷起来求得B的导数，然后将其转回去得到系数。

这⾥有个有趣的⼩细节，就是实际上，转回去之后，我们会不知道常数项，这应该怎么办呢？实际上常数项就是0，⾄于为什么，之后在exp部分会详细证明。

代码

#include

#defineLLlonglong

usingnamespacestd;

constintN=3e5+3;

constintM=998244353;

constintK=3;

inlineintrin()

{

ints=0;

boolbj=false;

charc=getchar();

for(;(c>'9'||c<'0')&&c!='-';c=getchar());

if(c=='-')bj=true,c=getchar();

for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^'0');

if(bj)s=-s;

returns;

}

inlineintprpr(intx,inty){return1LL*x*y%M;}

inlineintksm(intx,inty){intans=1;for(;y;y>>=1){if(y&1)ans=prpr(ans,x);x=prpr(x,x);}returnans;}

inlinevoidjh(int&x,int&y){if(x!=y)x^=y^=x^=y;return;}

constintKr=ksm(K,M-2);

intnum[N];

intlens;

inlinevoidinit(intL)

{

intlg=0;

for(lens=1;lens

for(inti=0;i>1]>>1)|((i&1)<

return;

}

inlinevoidNTT(int*a,inttag)

{

for(inti=0;inum[i])jh(a[i],a[num[i]]);

for(inti=1;i

{

intGyq=ksm(tag?K:Kr,(M-1)/(i<<1));

for(intj=0;j

{

intZjj=1;

for(intk=0;k

{

intx=a[j+k],y=prpr(a[j+k+i],Zjj);

a[j+k]=(x+y)%M;

a[j+k+i]=(x-y+M)%M;

}

}

}

if(!tag)

{

intGyq=ksm(lens,M-2);

for(inti=0;i

}

return;

}

intAlpha[N];

inlinevoidinv(int*a,int*b,intL)

{

if(L==1){b[0]=ksm(a[0],M-2);return;}

inv(a,b,(L+1)>>1);

init((L<<1)-1);

for(inti=0;i

for(inti=L;i

NTT(Alpha,1);

NTT(b,1);

for(inti=0;i

NTT(b,0);

for(inti=L;i

return;

}

inlinevoidder(int*a,intL){for(inti=1;i

intn;

inta[N];

intb[N];

intsl[N];

intsr[N];

intmain()

{

n=rin()-1;

for(inti=0;i<=n;i++)a[i]=rin();

inv(a,b,n+1);

init(n+n+1);

der(a,n+1);

NTT(a,1);

NTT(b,1);

for(inti=0;i

NTT(b,0);

sl[0]=sr[0]=1;

for(inti=1;i<=n;i++)sl[i]=prpr(sl[i-1],i);

sr[n]=ksm(sl[n],M-2);

for(inti=n-1;i>=1;i--)sr[i]=prpr(sr[i+1],i+1);

for(inti=n;i>=1;i--)b[i]=prpr(prpr(b[i-1],sr[i]),sl[i-1]);

b[0]=0;

for(inti=0;i<=n;i++)printf("%d",(b[i]%M+M)%M);printf("n");

return0;

}