洛谷P4725 【模板】多項(xiàng)式對(duì)數(shù)函數(shù)（多項(xiàng)式 ln）
題目大意
給你一個(gè) n ? 1 n-1 n?1次多項(xiàng)式 A ( x ) A(x) A(x)，求一個(gè) ? m o d ? x n \bmod x^n modxn下的多項(xiàng)式 B ( x ) B(x) B(x)，滿足 B ( x ) ≡ ln ? A ( x ) B(x)\equiv \ln A(x) B(x)≡lnA(x)。
在 ? m o d ? 998244353 \bmod 998244353 mod998244353下進(jìn)行， a i ∈ [ 0 , 998244353 ) a_i\in[0,998244353) ai?∈[0,998244353)且為整數(shù)。
保證 a 0 = 1 a_0=1 a0?=1
n ≤ 1 0 5 n\leq 10^5 n≤105
題解
前置知識(shí)：多項(xiàng)式乘法逆
依題意， B ( x ) = ln ? A ( x ) B(x)=\ln A(x) B(x)=lnA(x)，兩邊同時(shí)求導(dǎo)得
B ′ ( x ) = A ′ ( x ) A ( x ) B'(x)=\dfrac{A'(x)}{A(x)} B′(x)=A(x)A′(x)?
對(duì) A ( x ) A(x) A(x)進(jìn)行多項(xiàng)式乘法逆求出 1 A ( x ) \dfrac{1}{A(x)} A(x)1?，然后根據(jù)求導(dǎo)法則求出 A ′ ( x ) A'(x) A′(x)。然后 B ′ ( x ) = A ′ ( x ) ? 1 A ( x ) B'(x)=A'(x)\cdot \dfrac{1}{A(x)} B′(x)=A′(x)?A(x)1?，再積分一下得到 B ( x ) B(x) B(x)。
因?yàn)槌?shù)項(xiàng) a 0 = 1 a_0=1 a0?=1，所以 B ( x ) B(x) B(x)的常數(shù)項(xiàng) b 0 = 0 b_0=0 b0?=0。
時(shí)間復(fù)雜度為 O ( n log ? 2 n ) O(n\log^2 n) O(nlog2n)。
求導(dǎo)和積分
( x n ) ′ = n x n ? 1 (x^n)'=nx^{n-1} (xn)′=nxn?1文章來源：http://www.zghlxwxcb.cn/news/detail-435340.html
∫ x n d x = 1 n + 1 x n + 1 \int x^ndx=\dfrac{1}{n+1}x^{n+1} ∫xndx=n+11?xn+1文章來源地址http://www.zghlxwxcb.cn/news/detail-435340.html
code
#include<bits/stdc++.h>
using namespace std;
long long w,wn,f[500005],g[500005],a1[500005];
const long long G=3,mod=998244353;
long long mi(long long t,long long v){
if(!v) return 1;
long long re=mi(t,v/2);
re=re*re%mod;
if(v&1) re=re*t%mod;
return re;
}
void ch(long long *a,int l){
for(int i=1,j=l/2;i<l-1;i++){
if(i<j) swap(a[i],a[j]);
int k=l/2;
while(j>=k){
j-=k;k>>=1;
}
j+=k;
}
}
void ntt(long long *a,int l,int fl){
for(int i=2;i<=l;i<<=1){
if(fl==1) wn=mi(G,(mod-1)/i);
else wn=mi(G,mod-1-(mod-1)/i);
for(int j=0;j<l;j+=i){
w=1;
for(int k=j;k<j+i/2;k++,w=w*wn%mod){
long long t=a[k],u=w*a[k+i/2]%mod;
a[k]=(t+u)%mod;
a[k+i/2]=(t-u+mod)%mod;
}
}
}
if(fl==-1){
long long ny=mi(l,mod-2);
for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;
}
}
void solve(int l){
if(l==1){
g[0]=mi(f[0],mod-2);
return;
}
solve((l+1)/2);
int len=1;
while(len<2*l) len<<=1;
for(int i=0;i<l;i++) a1[i]=f[i];
for(int i=l;i<len;i++) a1[i]=0;
ch(a1,len);ch(g,len);
ntt(a1,len,1);
ntt(g,len,1);
for(int i=0;i<len;i++){
g[i]=(2-a1[i]*g[i]%mod+mod)%mod*g[i]%mod;
}
ch(g,len);
ntt(g,len,-1);
for(int i=l;i<len;i++) g[i]=0;
}
void qiudao(long long *a,int l){
for(int i=0;i<l;i++) a[i]=a[i+1]*(i+1)%mod;
a[l-1]=0;
}
void jifen(long long *a,int l){
for(int i=l;i>=1;i--) a[i]=a[i-1]*mi(i,mod-2)%mod;
a[0]=0;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&f[i]);
}
solve(n);
int len=1;
while(len<n*2) len<<=1;
qiudao(f,len);
ch(f,len);ch(g,len);
ntt(f,len,1);ntt(g,len,1);
for(int i=0;i<len;i++) f[i]=f[i]*g[i]%mod;
ch(f,len);
ntt(f,len,-1);
jifen(f,len);
for(int i=0;i<n;i++){
printf("%lld ",f[i]);
}
return 0;
}
到了這里，關(guān)于P4725 【模板】多項(xiàng)式對(duì)數(shù)函數(shù)（多項(xiàng)式 ln）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
