P4725 【模板】多项式对数函数（多项式 ln）

洛谷P4725 【模板】多项式对数函数（多项式 ln）

题目大意

给你一个$n-1$次多项式$A(x)$，求一个$\mathrm{mod}{x}^n$下的多项式$B(x)$，满足$B(x)\equiv \ln A(x)$。

在$\mathrm{mod}998244353$下进行，$a_i\in [0,998244353)$且为整数。

保证$a_0=1$

$n\le 10^5$

题解

前置知识：多项式乘法逆

依题意，$B(x)=\ln A(x)$，两边同时求导得

$$B^{\prime }(x)=\frac{A^{\prime }(x)}{A(x)}$$

对$A(x)$进行多项式乘法逆求出$\frac{1}{A(x)}$，然后根据求导法则求出$A^{\prime }(x)$。然后$B^{\prime }(x)=A^{\prime }(x)\cdot \frac{1}{A(x)}$，再积分一下得到$B(x)$。

因为常数项$a_0=1$，所以$B(x)$的常数项$b_0=0$。

时间复杂度为$O(n{\log }^{2}n)$。

求导和积分

$(x^n{)}^{\prime }=n{x}^{n-1}$

$\int x^{n}dx=\frac{1}{n+1}{x}^{n+1}$

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;
}