多项式全家桶

前置知识：

\(FFT,NTT\)

但主要是\(NTT\),常数小，不会损失精度，在模意义下更常用

我太懒，不想讲了

注意事项：

1.很多函数要清空，清空，清空
2.两个多项式在模意义下相乘时，要将高位赋值为\(0\)
3.开\(long\ long\)
4.要封装到一个\(namespace\)中，不然以后会很痛苦
5.我的代码常数很大，且用了#define int long long邪教，请勿模仿，不然很可能被卡常
6.下标默认从\(0\)开始

FFT/NTT

这个可以去看cmd的博客，这里就只贴个板子

namespace Math
{
	const int mod=998244353;
	inline int qpow(int a,int b=mod-2,int ans=1)
	{
		for(;b;b>>=1,(a*=a)%=mod) if(b&1) (ans*=a)%=mod;
		return ans;
	}
	inline int inv(int x){return qpow(x);}
}
namespace Poly
{
	const int mod=998244353;
	int rev[N];
    const double PI=acos(-1);
	struct node
	{
		double x,y;
		inline node(double xx=0,double yy=0){x=xx,y=yy;}
		inline node operator + (node a){return node(x+a.x,y+a.y);}
		inline node operator - (node a){return node(x-a.x,y-a.y);}
		inline node operator * (node a){return node(x*a.x-y*a.y,x*a.y+y*a.x);}
	}a[N],b[N];
	int rev[N];
	void fft(node *a,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
		for(int mid=1;mid<tot;mid<<=1)
		{
			node w=node(cos(PI/mid),tag*sin(PI/mid)),g=node(1,0),x,y;
			for(int i=0;i<tot;i+=mid<<1,g=node(1,0))
				for(int j=0;j<mid;++j,g=g*w)
					x=a[i+j],y=g*a[i+j+mid],
					a[i+j]=x+y,a[i+j+mid]=x-y;
		}
	}
	inline void FFT(int *A,int *B,int n,int m)
	{
		for(int i=0;i<=n;++i) a[i].x=A[i];
		for(int i=0;i<=m;++i) b[i].x=B[i];
		int bit=0,tot=1;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		fft(a,tot,1),fft(b,tot,1);
		for(int i=0;i<tot;++i) a[i]=a[i]*b[i];
		fft(a,tot,-1);
		for(int i=0;i<=n+m;++i) A[i]=(a[i].x/tot+0.5);
	}
	const int G=3,invG=Math::inv(G);
	inline void ntt(int *A,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(A[i],A[rev[i]]);
		for(int len=1;len<tot;len<<=1)
		{
			int Gn=Math::qpow(tag?G:invG,(mod-1)/len/2),x,y;
			for(int i=0;i<tot;i+=len*2)
			{
			 	int buf=1;
				for(int j=0;j<len;++j,(buf*=Gn)%=mod)
					x=A[i+j],y=buf*A[i+j+len]%mod,
					A[i+j]=(x+y)%mod,A[i+j+len]=(x-y+mod)%mod;
			}	
		}
	}
	inline void NTT(int *A,int *B,int n,int m)
	{
		int bit=0,tot=0;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?tot>>1:0);
		ntt(A,tot,1),ntt(B,tot,1);
		for(int i=0;i<tot;++i) A[i]=A[i]*B[i]%mod;
		ntt(A,tot,0);int invtot=Math::inv(tot);
		for(int i=0;i<tot;++i)A[i]=(A[i]*invtot)%mod;
	}
}

拉格朗日插值

记住一个式子

这个式子十分巧妙，我们发现\(y_i\prod_{i\neq j}\frac{x-x_j}{x_i-x_j}\)只在\(i\)的时候贡献\(y_i\),对其他\(n-1\)则贡献为\(0\),然后就结束了

namespace Poly
{
	const int mod=998244353;
	inline int langrange(int *A,int *B,int n,int k)
	{
		int ans=0;
		for(int i=1;i<=n;++i)
		{
			int s1=1,s2=1;
			for(int j=1;j<=n;++j)
				if(i!=j) (s1*=k-A[j])%=mod,(s2*=A[i]-A[j])%=mod;
			(ans+=B[i]*s1%mod*Math::inv(s2)%mod)%=mod;
		}
		return (ans+mod)%mod;
	}
}

多项式牛顿迭代

给出函数\(g(x)\),求出一个\(f(x)\)，使

我们递归考虑：

若我们已经知道\(t(x)\),使：

则：

因为泰勒展开:

则

将\(g(x),f(x),t(x)\)代入\(f(x),x,x_0\)，得到

因为:

所以

整理得到：

这个有什么用呢，等会可以拿来推导式子

多项式求逆

板子链接

给出一个\(n\)次多项式\(A(x)\)，求出一个\(n\)次多项式\(B(x)\),使

令\(g(x)=\frac{1}{x}-A(x)\),则\(g(B(x))\equiv 0\)

套路地令

则

然后递推+\(NTT\)求解就行了

namespace Poly
{
	const int mod=998244353;
	int rev[N];
	const int G=3,invG=Math::inv(G);
	inline int md(int x){return x>=mod?x-mod:x<0?x+mod:x;}
	inline void ntt(int *A,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(A[i],A[rev[i]]);
		for(int len=1;len<tot;len<<=1)
		{
			int Gn=Math::qpow(tag?G:invG,(mod-1)/len/2),x,y;
			for(int i=0;i<tot;i+=len*2)
			{
			 	int buf=1;
				for(int j=0;j<len;++j,(buf*=Gn)%=mod)
					x=A[i+j],y=buf*A[i+j+len]%mod,
					A[i+j]=md(x+y),A[i+j+len]=md(x-y);
			}	
		}
	}
	inline void NTT(int *A,int *B,int n,int m)
	{
		int bit=0,tot=0;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		ntt(A,tot,1),ntt(B,tot,1);
		for(int i=0;i<tot;++i) A[i]=A[i]*B[i]%mod;
		ntt(A,tot,0);int invtot=Math::inv(tot);
		for(int i=0;i<=n+m;++i)(A[i]=A[i]*invtot)%=mod;
	}
	int A[N],B[N];
	inline void niyuan(int *a,int *b,int n)
	{
		memset(A,0,n*16),memset(B,0,n*16);
		b[0]=Math::inv(a[0]);
		for(int l=2,m=1;l<=n*4;m<<=1,l<<=1)
		{
			for(int i=0;i<m;++i) A[i]=a[i],B[i]=b[i];
			for(int i=0;i<l;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?m:0);
			ntt(A,l,1),ntt(B,l,1);
			for(int i=0;i<l;++i) b[i]=((2-A[i]*B[i]%mod)*B[i]%mod+mod)%mod;
			ntt(b,l,0);int inv=Math::inv(l);
			for(int i=0;i<l;++i) (b[i]*=inv)%=mod;
			for(int i=m;i<l;++i) b[i]=0;
		}
	}
}

多项式开根

板子题链接

给定一个 \(n-1\) 次多项式 \(A(x)\)，求一个在 \({} \bmod x^n\) 意义下的多项式 \(B(x)\)，使得 \(B^2(x) \equiv A(x) \pmod{x^n}\)。若有多解，请取零次项系数较小的作为答案。

多项式的系数在 \({}\bmod 998244353\) 的意义下进行运算。

令\(g(x)=x^2-A(x)\),\(t(x)\)的定义与上面差不多，则

写多项式求逆就行了

namespace Poly
{
	const int mod=998244353;
	int rev[N];
	const int G=3,invG=Math::inv(G);
	inline int md(int x){return x>=mod?x-mod:x<0?x+mod:x;}
	inline void ntt(int *A,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(A[i],A[rev[i]]);
		for(int len=1;len<tot;len<<=1)
		{
			int Gn=Math::qpow(tag?G:invG,(mod-1)/len/2),x,y;
			for(int i=0;i<tot;i+=len*2)
			{
			 	int buf=1;
				for(int j=0;j<len;++j,(buf*=Gn)%=mod)
					x=A[i+j],y=buf*A[i+j+len]%mod,
					A[i+j]=md(x+y),A[i+j+len]=md(x-y);
			}	
		}
	}
	inline void NTT(int *A,int *B,int n,int m)
	{
		int bit=0,tot=0;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		ntt(A,tot,1),ntt(B,tot,1);
		for(int i=0;i<tot;++i) A[i]=A[i]*B[i]%mod;
		ntt(A,tot,0);int invtot=Math::inv(tot);
		for(int i=0;i<=n+m;++i)(A[i]=A[i]*invtot)%=mod;
	}
	int A[N],B[N];
	inline void niyuan(int *a,int *b,int n)
	{
		memset(A,0,n*16),memset(B,0,n*16);
		b[0]=Math::inv(a[0]);
		for(int l=2,m=1;l<n*4;m<<=1,l<<=1)
		{
			for(int i=0;i<m;++i) A[i]=a[i],B[i]=b[i];
			for(int i=0;i<l;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?m:0);
			ntt(A,l,1),ntt(B,l,1);
			for(int i=0;i<l;++i) b[i]=((2-A[i]*B[i]%mod)*B[i]%mod+mod)%mod;
			ntt(b,l,0);int inv=Math::inv(l);
			for(int i=0;i<l;++i) (b[i]*=inv)%=mod;
			for(int i=m;i<l;++i) b[i]=0;
		}
	}
	int Inv2=Math::inv(2),C[N],Inv[N];
	inline void kaigen(int *a,int *b,int n)
	{
		memset(C,0,n*16),memset(Inv,0,n*16);
		b[0]=1;
		for(int l=2,m=1;l<n*4;l<<=1,m<<=1)
		{
			for(int i=0;i<m;++i) C[i]=a[i];
			niyuan(b,Inv,m);
			for(int i=0;i<l;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?m:0);
			ntt(C,l,1),ntt(Inv,l,1);
			for(int i=0;i<l;++i) C[i]=C[i]*Inv[i]%mod;
			ntt(C,l,0);int inv=Math::inv(l);
			for(int i=0;i<l;++i) C[i]=C[i]*inv%mod;
			for(int i=1;i<m;++i) b[i]=Inv2*(b[i]+C[i])%mod;
		}
	}
}

多项式求导和积分

这个就跟数学上的差不多，可以自己学一下(一般积分时忽略常数\(C\))

代码:

namespace Poly
{
    inline void qiudao(int *A,int *B,int n)
	{
		for(int i=1;i<n;++i) B[i-1]=i*A[i]%mod;
		return B[n-1]=0,void();
	}
	inline void jifen(int *A,int *B,int n)
	{
		for(int i=1;i<n;++i) B[i]=A[i-1]*Math::inv(i)%mod;
		return B[0]=0,void();
	}
}

多项式对数函数(多项式ln)

板子题链接

给出 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\)，满足 \(B(x) \equiv \ln A(x)\).

在 \(\text{mod } 998244353\) 下进行，且 \(a_i \in [0, 998244353) \cap \mathbb{Z}\)

我们手推一下式子：

然后只用写求导，积分和求逆三个板子就行了

分治FFT

链接

给定序列 \(g_{1\dots n - 1}\)，求序列 \(f_{0\dots n - 1}\)。

其中 \(f_i=\sum_{j=1}^if_{i-j}g_j\)，边界为 \(f_0=1\)。

答案对 \(998244353\) 取模。

就跟\(CDQ\)分治一样

具体实现看代码：

namespace Poly
{
	const int mod=998244353;
	int rev[N];
	const int G=3,invG=Math::inv(G);
	inline void ntt(int *A,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(A[i],A[rev[i]]);
		for(int len=1;len<tot;len<<=1)
		{
			int Gn=Math::qpow(tag?G:invG,(mod-1)/len/2),x,y;
			for(int i=0;i<tot;i+=len*2)
			{
			 	int buf=1;
				for(int j=0;j<len;++j,(buf*=Gn)%=mod)
					x=A[i+j],y=buf*A[i+j+len]%mod,
					A[i+j]=(x+y)%mod,A[i+j+len]=(x-y+mod)%mod;
			}	
		}
	}
	inline void NTT(int *A,int *B,int n,int m)
	{
		int bit=0,tot=0;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?tot>>1:0);
		ntt(A,tot,1),ntt(B,tot,1);
		for(int i=0;i<tot;++i) A[i]=A[i]*B[i]%mod;
		ntt(A,tot,0);int invtot=Math::inv(tot);
		for(int i=0;i<tot;++i)A[i]=(A[i]*invtot)%mod;
	}
	int A[N],B[N];
	void fenzhi(int *a,int *b,int l,int r)
	{
		if(l==r) return;
		int mid=(l+r)>>1,len=r-l+1;
		fenzhi(a,b,l,mid);
		for(int i=0;i<=4*len;++i) A[i]=B[i]=0;
		for(int i=0;i<=mid-l;++i) A[i]=b[i+l];
		for(int i=0;i<len;++i) B[i]=a[i+1];
		NTT(A,B,mid-l+1,len);
		for(int i=mid+1;i<=r;++i) b[i]=(b[i]+A[i-l-1])%mod;
		fenzhi(a,b,mid+1,r);
	}
}

多项式指数函数(多项式exp)

链接

给出 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\)，满足 \(B(x) \equiv \text e^{A(x)}\)。系数对 \(998244353\) 取模。

也是推式子,令\(g(x)=\ln x-A(x)\),\(t(x)\)的定义和上面相似，则

写多项式\(\ln\)就行了

常数巨大的\(O(n\log n)\)

也有\(O(n\log^2 n)\)的分治\(NTT\)写法

然后分治NTT就行了(据说跑的比\(O(n\log n)\)快)

多项式快速幂

链接

给定一个 \(n-1\) 次多项式 \(A(x)\)，求一个在 \(\bmod\ x^n\) 意义下的多项式 \(B(x)\)，使得 \(B(x) \equiv (A(x))^k \ (\bmod\ x^n)\)。

多项式的系数在 \(\bmod\ 998244353\) 的意义下进行运算。

推式子:

写个多项式\(\ln\)和多项式\(exp\)就行了

namespace Poly
{
	const int mod=998244353;
	int rev[N];
	const int G=3,invG=Math::inv(G);
	inline void ntt(int *A,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(A[i],A[rev[i]]);
		for(int len=1;len<tot;len<<=1)
		{
			int Gn=Math::qpow(tag?G:invG,(mod-1)/len/2),x,y;
			for(int i=0;i<tot;i+=len*2)
			{
			 	int buf=1;
				for(int j=0;j<len;++j,(buf*=Gn)%=mod)
					x=A[i+j],y=buf*A[i+j+len]%mod,
					A[i+j]=(x+y)%mod,A[i+j+len]=(x-y+mod)%mod;
			}	
		}
	}
	inline void NTT(int *A,int *B,int n,int m)
	{
		int bit=0,tot=0;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?tot>>1:0);
		ntt(A,tot,1),ntt(B,tot,1);
		for(int i=0;i<tot;++i) A[i]=A[i]*B[i]%mod;
		ntt(A,tot,0);int invtot=Math::inv(tot);
		for(int i=0;i<tot;++i)A[i]=(A[i]*invtot)%mod;
	}
	inline void qiudao(int *A,int *B,int n)
	{
		for(int i=0;i<4*n;++i) B[i]=0;
		for(int i=1;i<n;++i) B[i-1]=i*A[i]%mod;
		return B[n-1]=0,void();
	}
	inline void jifen(int *A,int *B,int n)
	{
		for(int i=0;i<4*n;++i) B[i]=0;
		for(int i=1;i<n;++i) B[i]=A[i-1]*Math::inv(i)%mod;
		return B[0]=0,void();
	}
	int A[N],B[N];
	inline void qiuni(int *a,int *b,int n)
	{
		for(int i=0;i<4*n;++i) A[i]=B[i]=b[i]=0;
		b[0]=Math::inv(a[0]);
		for(int l=2,m=1;l<n*4;m<<=1,l<<=1)
		{
			for(int i=0;i<m;++i) A[i]=a[i],B[i]=b[i];
			for(int i=0;i<l;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?m:0);
			ntt(A,l,1),ntt(B,l,1);
			for(int i=0;i<l;++i) b[i]=((2-A[i]*B[i]%mod)*B[i]%mod+mod)%mod;
			ntt(b,l,0);int inv=Math::inv(l);
			for(int i=0;i<l;++i) (b[i]*=inv)%=mod;
			for(int i=m;i<l;++i) b[i]=0;
		}
	}
	int C[N],Inv[N];
	inline void ln(int *a,int *b,int n)
	{
		for(int i=0;i<4*n;++i) b[i]=C[i]=Inv[i]=0;
		qiudao(a,C,n),qiuni(a,Inv,n);
		NTT(C,Inv,n,n);
		jifen(C,b,n);
	}
	int D[N],E[N];
	inline void exp(int *a,int *b,int n)
	{
		for(int i=0;i<4*n;++i) b[i]=D[i]=E[i]=0;
		b[0]=1;
		for(int l=4,m=2;l<=n*4;l<<=1,m<<=1)
		{
			for(int i=m;i<l;++i) D[i]=E[i]=0;
			for(int i=0;i<m;++i) E[i]=a[i];
			ln(b,D,m);
			for(int i=0;i<m;++i) E[i]=(mod-D[i]+E[i])%mod;
			(E[0]+=1)%=mod;
			NTT(b,E,l,l);
			for(int i=m;i<l;++i) b[i]=0;
		}
	}
	int H[N];
	inline void pow(int *a,int *b,int n,int k)
	{
		ln(a,H,n);
		for(int i=0;i<n;++i) (H[i]*=k)%=mod;
		exp(H,b,n);
	}
}

目前的全家桶

namespace Math
{
	const int mod=998244353;
	inline int qpow(int a,int b=mod-2,int ans=1)
	{
		for(;b;b>>=1,(a*=a)%=mod) if(b&1) (ans*=a)%=mod;
		return ans;
	}
	inline int inv(int x){return qpow(x);}
}
namespace Poly
{
	const int mod=998244353;
	int rev[N];
	inline int langrange(int *A,int *B,int n,int k)
	{
		int ans=0;
		for(int i=1;i<=n;++i)
		{
			int s1=1,s2=1;
			for(int j=1;j<=n;++j)
				if(i!=j) (s1*=k-A[j])%=mod,(s2*=A[i]-A[j])%=mod;
			(ans+=B[i]*s1%mod*Math::inv(s2)%mod)%=mod;
		}
		return (ans+mod)%mod;
	}
	const double PI=acos(-1);
	struct node
	{
		double x,y;
		inline node(double xx=0,double yy=0){x=xx,y=yy;}
		inline node operator + (node a){return node(x+a.x,y+a.y);}
		inline node operator - (node a){return node(x-a.x,y-a.y);}
		inline node operator * (node a){return node(x*a.x-y*a.y,x*a.y+y*a.x);}
	}a[N],b[N];
	int rev[N];
	void fft(node *a,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
		for(int mid=1;mid<tot;mid<<=1)
		{
			node w=node(cos(PI/mid),tag*sin(PI/mid)),g=node(1,0),x,y;
			for(int i=0;i<tot;i+=mid<<1,g=node(1,0))
				for(int j=0;j<mid;++j,g=g*w)
					x=a[i+j],y=g*a[i+j+mid],
					a[i+j]=x+y,a[i+j+mid]=x-y;
		}
	}
	inline void FFT(int *A,int *B,int n,int m)
	{
		for(int i=0;i<=n;++i) a[i].x=A[i];
		for(int i=0;i<=m;++i) b[i].x=B[i];
		int bit=0,tot=1;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		fft(a,tot,1),fft(b,tot,1);
		for(int i=0;i<tot;++i) a[i]=a[i]*b[i];
		fft(a,tot,-1);
		for(int i=0;i<=n+m;++i) A[i]=(a[i].x/tot+0.5);
	}
	const int G=3,invG=Math::inv(G);
	inline void ntt(int *A,int tot,int tag)
	{
		for(int i=0;i<tot;++i) if(i<rev[i]) swap(A[i],A[rev[i]]);
		for(int len=1;len<tot;len<<=1)
		{
			int Gn=Math::qpow(tag?G:invG,(mod-1)/len/2),x,y;
			for(int i=0;i<tot;i+=len*2)
			{
			 	int buf=1;
				for(int j=0;j<len;++j,(buf*=Gn)%=mod)
					x=A[i+j],y=buf*A[i+j+len]%mod,
					A[i+j]=(x+y)%mod,A[i+j+len]=(x-y+mod)%mod;
			}	
		}
	}
	inline void NTT(int *A,int *B,int n,int m)
	{
		int bit=0,tot=0;
		while((1<<bit)<n+m+1) ++bit;tot=1<<bit;
		for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?tot>>1:0);
		ntt(A,tot,1),ntt(B,tot,1);
		for(int i=0;i<tot;++i) A[i]=A[i]*B[i]%mod;
		ntt(A,tot,0);int invtot=Math::inv(tot);
		for(int i=0;i<tot;++i)A[i]=(A[i]*invtot)%mod;
	}
	inline void qiudao(int *A,int *B,int n)
	{
		for(int i=0;i<4*n;++i) B[i]=0;
		for(int i=1;i<n;++i) B[i-1]=i*A[i]%mod;
		return B[n-1]=0,void();
	}
	inline void jifen(int *A,int *B,int n)
	{
		for(int i=0;i<4*n;++i) B[i]=0;
		for(int i=1;i<n;++i) B[i]=A[i-1]*Math::inv(i)%mod;
		return B[0]=0,void();
	}
	int A[N],B[N];
	inline void qiuni(int *a,int *b,int n)
	{
		for(int i=0;i<4*n;++i) A[i]=B[i]=b[i]=0;
		b[0]=Math::inv(a[0]);
		for(int l=2,m=1;l<n*4;m<<=1,l<<=1)
		{
			for(int i=0;i<m;++i) A[i]=a[i],B[i]=b[i];
			for(int i=0;i<l;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?m:0);
			ntt(A,l,1),ntt(B,l,1);
			for(int i=0;i<l;++i) b[i]=((2-A[i]*B[i]%mod)*B[i]%mod+mod)%mod;
			ntt(b,l,0);int inv=Math::inv(l);
			for(int i=0;i<l;++i) (b[i]*=inv)%=mod;
			for(int i=m;i<l;++i) b[i]=0;
		}
	}
	int Inv2=Math::inv(2),C[N],Inv[N];
	inline void kaigen(int *a,int *b,int n)
	{
		memset(C,0,n*16),memset(Inv,0,n*16);
		b[0]=1;
		for(int l=2,m=1;l<n*4;l<<=1,m<<=1)
		{
			for(int i=0;i<m;++i) C[i]=a[i];
			niyuan(b,Inv,m);
			for(int i=0;i<l;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?m:0);
			ntt(C,l,1),ntt(Inv,l,1);
			for(int i=0;i<l;++i) C[i]=C[i]*Inv[i]%mod;
			ntt(C,l,0);int inv=Math::inv(l);
			for(int i=0;i<l;++i) C[i]=C[i]*inv%mod;
			for(int i=1;i<m;++i) b[i]=Inv2*(b[i]+C[i])%mod;
		}
	inline void ln(int *a,int *b,int n)
	{
		for(int i=0;i<4*n;++i) b[i]=C[i]=Inv[i]=0;
		qiudao(a,C,n),qiuni(a,Inv,n);
		NTT(C,Inv,n,n);
		jifen(C,b,n);
	}
	void fenzhi(int *a,int *b,int l,int r)
	{
		if(l==r) return;
		int mid=(l+r)>>1,len=r-l+1;
		fenzhi(a,b,l,mid);
		for(int i=0;i<=4*len;++i) A[i]=B[i]=0;
		for(int i=0;i<=mid-l;++i) A[i]=b[i+l];
		for(int i=0;i<len;++i) B[i]=a[i+1];
		NTT(A,B,mid-l+1,len);
		for(int i=mid+1;i<=r;++i) b[i]=(b[i]+A[i-l-1])%mod;
		fenzhi(a,b,mid+1,r);
	}
	int D[N],E[N];
	inline void exp(int *a,int *b,int n)
	{
		for(int i=0;i<4*n;++i) b[i]=D[i]=E[i]=0;
		b[0]=1;
		for(int l=4,m=2;l<=n*4;l<<=1,m<<=1)
		{
			for(int i=m;i<l;++i) D[i]=E[i]=0;
			for(int i=0;i<m;++i) E[i]=a[i];
			ln(b,D,m);
			for(int i=0;i<m;++i) E[i]=(mod-D[i]+E[i])%mod;
			(E[0]+=1)%=mod;
			NTT(b,E,l,l);
			for(int i=m;i<l;++i) b[i]=0;
		}
	}
	int H[N];
	inline void pow(int *a,int *b,int n,int k)
	{
		ln(a,H,n);
		for(int i=0;i<n;++i) (H[i]*=k)%=mod;
		exp(H,b,n);
	}
}

留的坑

多项式除法，多项式取模，\(FWT\),多项式三角函数，多项式反三角函数
一车东西的任意模数版
多项式多点求值|快速插值
多项式平移|连续点值平移
常系数齐次线性递推
普通多项式与下降幂多项式互化
在生成函数中的应用
可能会(gu)填(gu)坑(gu)的(gu)

本栏目推荐文章
• 多项式定积分计算软件2025 64位WIN版下载Polynomial definite integral calculation software 2025 64 bit WIN version download
• DevOps常用工具全家桶，实现高效运维和交付
• 【算法设计与分析】(二)分治_更新中①：二分搜索、计数、选择、最近点对、凸包、多项式乘法、矩阵乘法、主定理&递归树、傅里叶。苏大计科院研一期末复习笔记
• 「学习笔记」组合计数：格路计数、二项式反演、斯特林数与 Min-max 容斥
• 天翼云亮相操作系统大会&openEuler Summit 2023，斩获多项大奖！
• 西电数据结构oj 单链表 多项式加减法
• 多项式exp/牛顿迭代
• 多项式的逆元
• 在任意代数结构上的多项式乘法 学习笔记
• 计算给定多项式的值

多项式 全家多项式 全家 全家 全家vue vue3全家vue笔记 全家tarjan 全家burry 全家computed属性vue3 javascript全家vue 全家devserver参数vue3 全家request文件axios