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

这篇具有很好参考价值的文章主要介绍了P4725 【模板】多项式对数函数（多项式 ln）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

题目大意

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

在 $\bmod 998244353$ 下进行， $a_i\in[0,998244353)$ 且为整数。

保证 $a_0=1$

$n\leq 10^5$

题解

前置知识：多项式乘法逆

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

$B'(x)=\dfrac{A'(x)}{A(x)}$

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

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

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

求导和积分

$x^n)'=nx^{n-1}$

$\int x^ndx=\dfrac{1}{n+1}x^{n+1}$ 文章来源地址https://www.toymoban.com/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;
}