多项式乘法

略，这个太水了（从另一个方面，其实这是最难的，这取决于你写不写证明）。

多项式求逆

多项式\(\ln\)

多项式\(\exp\)

事实上，这几种多项式算法是包含关系，从最后一个开始，每一个都包含了以前所有的算法。
代码（其实这是从多项式\(\exp\)板子题那儿复制下来的，但它本身就包含了前面几种）：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5,mod=998244353,IG=332748118;
int n,lim,tra[4*N+10];
ll a[4*N+10],a1[4*N+10],b[4*N+10],c[4*N+10],d[4*N+10];
inline int Read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!=‘-‘) ch=getchar();
	ch==‘-‘?f=-1:x=ch-‘0‘;
	while(isdigit(ch=getchar())) x=x*10+ch-‘0‘;
	return x*f;
}
inline ll ksm(ll x,int k)
{
	ll ret=1;
	while(k)
	{
		if(k&1) ret=ret*x%mod;
		x=x*x%mod,k>>=1;
	}
	return ret;
}
inline void ntt(ll *A,int opt)
{
	for(register int i=0;i<lim;++i) 
		if(i<tra[i]) swap(A[i],A[tra[i]]);
	for(register int i=2;i<=lim;i<<=1)
	{
		int len=i>>1;
		ll wn=ksm(opt==1?3:IG,(mod-1)/i);
		for(register int j=0;j<lim;j+=i)
		{
			ll buf=1;
			for(register int k=j;k<j+len;++k)
			{
				ll tmp=buf*A[k+len]%mod;
				A[k+len]=(A[k]-tmp+mod)%mod,A[k]=(A[k]+tmp)%mod;
				buf=buf*wn%mod;
			}
		}
	}
	if(opt==1) return;
	ll inv=ksm(lim,mod-2);
	for(register int i=0;i<lim;++i) A[i]=A[i]*inv%mod;
}
inline void p_inv(int depth,ll *A,ll *B)
{
	if(depth==1) {B[0]=ksm(A[0],mod-2);return;}
	p_inv((depth+1)>>1,A,B);
	lim=1;
	while(lim<2*depth) lim<<=1;
	for(register int i=0;i<lim;++i) tra[i]=(tra[i>>1]>>1)|((i&1)?lim>>1:0);
	for(register int i=0;i<depth;++i) c[i]=A[i];
	for(register int i=depth;i<lim;++i) c[i]=0;
	ntt(B,1),ntt(c,1);
	for(register int i=0;i<lim;++i) B[i]=(2ll-B[i]*c[i]%mod+mod)%mod*B[i]%mod;
	ntt(B,-1);
	for(register int i=depth;i<lim;++i) B[i]=0;
}
inline void p_ln(int n,ll *A,ll *B)
{
	for(register int i=0;i<=2*n;++i) a1[i]=B[i]=0;
	for(register int i=1;i<n;++i) a1[i-1]=i*A[i]%mod;a1[n-1]=0;
	p_inv(n,A,B);
	lim=1;
	while(lim<2*n) lim<<=1;
	for(register int i=0;i<lim;++i) tra[i]=(tra[i>>1]>>1)|((i&1)?lim>>1:0);
	ntt(a1,1),ntt(B,1);
	for(register int i=0;i<lim;++i) a1[i]=B[i]*a1[i]%mod;
	ntt(a1,-1);
	for(register int i=0;i<n-1;++i) B[i+1]=a1[i]*ksm(i+1,mod-2)%mod;B[0]=0;
}
inline void p_exp(int depth,ll *A,ll *B)
{
	if(depth==1) {B[0]=1;return;}
	p_exp((depth+1)>>1,A,B);
	lim=1;
	while(lim<2*depth) lim<<=1;
	for(register int i=0;i<lim;++i) tra[i]=(tra[i>>1]>>1)|((i&1)?lim>>1:0);
	p_ln(depth,B,d);
	for(register int i=0;i<depth;++i) d[i]=(A[i]-d[i]+mod)%mod;
	for(register int i=depth;i<lim;++i) d[i]=0;
	d[0]++;
	ntt(B,1),ntt(d,1);
	for(register int i=0;i<lim;++i) B[i]=d[i]*B[i]%mod;
	ntt(B,-1);
	for(register int i=depth;i<lim;++i) B[i]=0;
}
int main()
{
	n=Read();
	for(register int i=0;i<n;++i) a[i]=Read();
	p_exp(n,a,b);
	for(register int i=0;i<n;++i) printf("%lld ",b[i]);
	return 0;
}

一般来说这些是比较常用的（大概是吧），剩下的那些以后慢慢更新。

多项式全家桶（结论版）

原文：https://www.cnblogs.com/SKTT1Faker/p/13344423.html