多项式Polynomial

前置知识$\text{NTT}$

所有操作均在对$P=\text{998244353}$取模下进行

代码在最下面

下文中$\pmod {x^n}$表示求出了多项式的前$n$项

$[x^i]F(x)$表示$F(x)$第$i$项的系数

每个小问题的模板题都可以在洛谷上找到

---

1.多项式求乘法逆

(为什么叫做乘法逆?因为还有求$G(x)=\frac{1} {F(x)}\pmod {M(x)}的$)

求 $G(x)\equiv \frac{1} {F(x)} \pmod {x^n}$

形象化的理解就是$F(x)\cdot G(x) \pmod {x^n}$只有第一项是$1$，其他项都是$0$

这个由于是第一个操作，很多人还并不是很能理解多项式操作到底是什么东西，所以讲多一点

Part1 O($n^2$)

为了便于理解这个问题，先考虑一个最简单的模拟

$[x^i]F\cdot G(x)=\sum [x^j]F(x)[x^{i-j}]G(x)$

第一项$[x^0]G(x)=\frac{1} {[x^0]F(0)} \pmod P$，因此求逆的前提条件是$[x^0]F(x)\ne 0$

考虑从$1$到$n-1$依次求出每一项，先从前面的项中得到所有$j>0$的和$Sum$，然后带入$j=0$时知道

$$[x^i]G(x)=-\frac{Sum=\sum_{j=1}^{j\leq i}[x^j]F(x)[x^{i-j}]G(x)} {[x^0]F(0)}$$ $$\$$

---

Part2 O($n\log^2n$)

上面这个式子是一个类似$dp$转移的东西，可以直接分治NTT优化掉

$$\$$

---

Part3 $O(n\log n)$

考虑递归求解，设已经求出了

$$H(x)\equiv \frac{1} {F(x)},\pmod {x^{\frac{n} {2} }}$$

其中递归边界是$n=1$时,$[x^0]G(x)=\frac{1} {[x^0]F(0)} \pmod P$，因此求逆的前提条件是$[x^0]F(x)\ne 0$

则

$$H(x)\equiv G(x)\pmod {x^{\frac{n} {2} }}$$ $$H(x)-G(x)\equiv 0\pmod {x^{\frac{n} {2} }}$$

我们对于$H(x)-G(x)$平方，结果的前$n$项不可能由两个$\ge \frac{n} {2}$的项相乘得到，而前$\frac{n} {2}$项都是$0$，所以

$$(H(x)-G(x))^2\equiv 0\pmod {x^n}$$

所以通过平方可以扩大模数，这很常用

展开平方的式子

$$H(x)^2-2G(x)H(x)+G(x)^2\equiv 0\pmod {x^n}$$

两边乘上$F(x)$

$$H(x)^2F(x)-2H(x)+G(x)\equiv 0\pmod {x^n}$$ $$G(x)\equiv 2H(x)-H(x)^2F(x)\pmod {x^n}$$

带入这个式子倍增求解即可

分析复杂度，每次有一个$H(x)^2F(x)$，可以通过$NTT$求出，倍增过程中访问的长度是$O(n+\frac{n} {2}+\frac{n} {4}…)=O(n)$

所以总复杂度就是$O(n\log n)$

$$\$$

---

2.多项式开根号

求$G(x)^2\equiv F(x) \pmod {x^n}$

同样的，递归求解，设已经求出了，递归边界是$n=1$时,$[x^0]G(x)=\sqrt{[x^0]F(x)}\pmod P$

可以发现我们需要求二次剩余。。。但是一般题目保证了$[x^0]F(x)\in\{0,1\}$

设已经求出$H(x)^2\equiv F(x) \pmod{ x^{\lceil \frac{n} {2} \rceil} }$

$$H(x)\equiv G(x) \pmod {x^{\lceil \frac{n} {2}\rceil} }$$ $$H(x)^2-2G(x)H(x)+G(x)^2\equiv 0\pmod {x^n}$$ $$H(x)^2-2G(x)H(x)+F(x)\equiv 0 \pmod {x^n}$$ $$G(x)\equiv \frac{H(x)^2+F(x)} {2H(x)} \pmod {x^n}$$

带入这个式子倍增求解即可

复杂度为$O(n\log n)$

$$\$$

---

3.多项式求$\ln$

$$G(x)\equiv \ln F(x) \pmod {x^n}$$ $$G'(x)\equiv F'(x)\frac{1} {F(x)} \pmod {x^n}$$

求出$G’(x)$，然后求原函数即可

复杂度为$O(n\log n)$

$$\$$

---

4.多项式求exp(牛顿迭代)

把题目转化为，对于函数$f(G)=\ln G-F$

求出在$\mod x^n$意义下的零点

其中$f(x)=\ln x-c$

考虑迭代求解，设已经求出$H(x)=e^{F(x)}\pmod {x^{\frac{n} {2} }}$

边界条件是$[x^0]H(x)=e^{[x^0]F(x)}$(由于没有办法求$e^x$在模意义下的值，所以通常必须要满足$[x^0]F(x)=0$)

带入牛顿迭代的结果

$$G=H-\frac{f(H)} {f'(H)}=H(F-\ln H+1)$$

每次求$ln $复杂度和$NTT$相同，所以总复杂度为$O(n\log n)$

事实上这个还有优化的余地，就是在求$ln$的时候，多项式逆的部分可以同步倍增求出，不需要每次都倍增一下(但是好像效果并不是特别明显)

$$\$$ $$\$$

---

5.多项式$k$次幂

$G(x)\equiv F(x)^k\pmod {x^n}$

$\ln G(x)=k \ln F(x) \pmod {x^n}$

求出$\ln G(x)$之后，$exp$回来即可

由于要求$ln$，所以这样求的条件是$[x^0]F(x)=1$

很显然这个方法对于开根号也是适用的

复杂度$O(n\log n)$

$$\$$ $$\$$ $$\$$

---

6.多项式带余除法

可以参考神仙miskcoo的博客

应用：多项式多点求值，常系数线性齐次递推

$$\$$

以上是基本运算，如果不想继续吸多项式请直接跳到最下面的代码

多项式与点值式

下降幂多项式初步

$$\$$ $$\$$

---

$$\$$ $$\$$ $$\$$

---

所有的操作均用$\text{vector} $来实现，主要是为了理清思路，并且清零问题上会比较容易解决，同时对于每次计算完多项式的长度的要求会显得更加严格

---

稍微整理了一下，没怎么卡过常，所以应该还是比较可读的

代码总览(请使用C++11,O2编译运行)

基本运算的总模板题Loj - 150

#include<bits/stdc++.h>
using namespace std;

#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))

#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int MaxK=19;
const int N=(1<<MaxK)+10,P=998244353;

int n,k;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

namespace Polynomial{
	typedef vector <int> Poly;
	void Show(Poly a,int k=0){ 
		if(!k){ for(int i:a) printf("%d ",i); puts(""); }
		else for(int i:a) printf("%d\n",i);
	}
	int K;
	int rev[N];
	int Mod_Inv[N],Fac[N],FInv[N];
	int w[1<<MaxK|10];

	void Init_w() { // NTT的系数预处理
		K=MaxK;
		//while((1<<K)<=n+1) K++;
		int t=qpow(3,(P-1)>>K);
		K--;
		w[1<<K]=1;
		rep(i,(1<<K)+1,(1<<(K+1))-1) w[i]=1ll*w[i-1]*t%P;
		drep(i,(1<<K)-1,1) w[i]=w[i<<1];

		Mod_Inv[0]=Mod_Inv[1]=Fac[0]=Fac[1]=FInv[0]=FInv[1]=1;
		rep(i,2,(1<<K)) {
			Mod_Inv[i]=1ll*(P-P/i)*Mod_Inv[P%i]%P; 
			FInv[i]=1ll*FInv[i-1]*Mod_Inv[i]%P;
			Fac[i]=1ll*Fac[i-1]*i%P;
		}
	}
	int Init(int n){ // 翻转数组预处理
		int R=1,cc=-1;
		while(R<n) R<<=1,cc++;
		rep(i,1,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<cc);
		return R;
	}
	void NTT(int n,Poly &a,int f){ // NTT板子
		rep(i,0,n-1) if(rev[i]<i) swap(a[i],a[rev[i]]);
		for(int i=1;i<n;i<<=1) {
			int *e=w+i;
			for(int l=0;l<n;l+=i*2) {
				for(int j=l;j<l+i;++j) {
					int t=1ll*a[j+i]*e[j-l]%P;
					a[j+i]=a[j]-t,Mod2(a[j+i]);
					a[j]+=t,Mod1(a[j]);
				}
			}
		}
		if(f==-1) {
			reverse(a.begin()+1,a.begin()+n);
			ll base=Mod_Inv[n];
			rep(i,0,n-1) a[i]=a[i]*base%P;
		}
	}
	
	Poly operator * (Poly a,Poly b){
		int n=a.size()+b.size()-1;
		int R=Init(n);
		a.resize(R),b.resize(R);
		NTT(R,a,1),NTT(R,b,1);
		rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
		NTT(R,a,-1);
		a.resize(n);
		return a;
	}

	Poly operator + (Poly a,Poly b) { 
		int n=max(a.size(),b.size());
		a.resize(n),b.resize(n);
		rep(i,0,n-1) a[i]+=b[i],Mod1(a[i]);
		return a; 
	}
	Poly operator - (Poly a,Poly b) { 
		int n=max(a.size(),b.size());
		a.resize(n),b.resize(n);
		rep(i,0,n-1) a[i]-=b[i],Mod2(a[i]);
		return a; 
	}

	Poly Inv(Poly a) { // 多项式乘法逆，注意这里求出的是前a.size()项
		int n=a.size();
		if(n==1) return Poly{(int)qpow(a[0],P-2)};
		Poly b=a; b.resize((n+1)/2); b=Inv(b);
		int R=Init(n<<1);
		a.resize(R),b.resize(R);
		NTT(R,a,1),NTT(R,b,1);
		rep(i,0,R-1) a[i]=(2-1ll*a[i]*b[i]%P+P)*b[i]%P;
		NTT(R,a,-1);
		a.resize(n);
		return a;
	}
    
	Poly operator / (Poly a,Poly b){ // 多项式带余除法
		reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
		int n=a.size(),m=b.size();
		a.resize(n-m+1),b.resize(n-m+1),b=Inv(b);
		a=a*b,a.resize(n-m+1);
		reverse(a.begin(),a.end());
		return a;
	}
	Poly operator % (Poly a,Poly b) { // 多项式取模
		int n=b.size()-1;
		if((int)a.size()<=n) return a;
		Poly t=a/b;
		if((int)t.size()>n) t.resize(n);
		t=t*b; t.resize(n); a.resize(n);
		return a-t;
	}

	int Quad(int a,int k=0) { // 二次剩余(不是原根法),用于求Sqrt
		if(a<=1) return a;
		ll x;
		while(1) {
			x=1ll*rand()*rand()%P;
			if(qpow((x*x-a+P)%P,(P-1)/2)!=1) break;
		}
		ll w=(x*x-a+P)%P;
		ll rx=1,ry=0,xx=x,xy=1,tx,ty;
		int d=(P+1)/2;
		while(d) {
			if(d&1) {
				tx=(rx*xx+ry*xy%P*w)%P,ty=(rx*xy+ry*xx)%P;
				rx=tx,ry=ty;
			}
			tx=(xx*xx+xy*xy%P*w)%P,ty=2*xx*xy%P;
			xx=tx,xy=ty;
			d>>=1;
		}
		ll res=(rx%P+P)%P;
		if(k) res=min(res,(P-res)%P);
		return res;
	}
	Poly Sqrt(Poly a){ // 多项式开根号
		int n=a.size();
		if(n==1) return Poly{Quad(a[0],1)};
		Poly b=a; b.resize((n+1)/2),b=Sqrt(b),b.resize(n);
		Poly c=Inv(b);
		int R=Init(n*2);
		a.resize(R),c.resize(R);
		NTT(R,a,1),NTT(R,c,1);
		rep(i,0,R-1) a[i]=1ll*a[i]*c[i]%P;
		NTT(R,a,-1);
		a.resize(n);
		rep(i,0,n-1) a[i]=1ll*(P+1)/2*(a[i]+b[i])%P;
		return a;
	}

	Poly Deri(Poly a){ //求导
		rep(i,1,a.size()-1) a[i-1]=1ll*i*a[i]%P;
		a.pop_back();
		return a;
	}
	Poly IDeri(Poly a) { //原函数
		a.pb(0);
		drep(i,a.size()-1,1) a[i]=1ll*a[i-1]*Mod_Inv[i]%P;
		a[0]=0;
		return a;
	}
    
	Poly Ln(Poly a){ // 多项式求Ln
		int n=a.size();
		a=Inv(a)*Deri(a),a.resize(n-1);
		return IDeri(a);
	}
	Poly Exp(Poly a){ // 多项式Exp
		int n=a.size();
		if(n==1) return Poly{1};
		Poly b=a; b.resize((n+1)/2),b=Exp(b); b.resize(n);
		Poly c=Ln(b);
		rep(i,0,n-1) c[i]=a[i]-c[i],Mod2(c[i]);
		c[0]++,b=b*c;
		b.resize(n);
		return b;
	}
	Poly Pow(Poly x,int k) { // 多项式k次幂
		x=Ln(x);
		rep(i,0,x.size()-1) x[i]=1ll*x[i]*k%P;
		return Exp(x);
	}

	Poly EvaluateTemp[N<<1];
	void EvaluateSolve1(Poly &a,int l,int r,int p=1){
		if(l==r) { EvaluateTemp[p]=Poly{P-a[l],1}; return; } 
		int mid=(l+r)>>1;
		EvaluateSolve1(a,l,mid,p<<1),EvaluateSolve1(a,mid+1,r,p<<1|1);
		EvaluateTemp[p]=EvaluateTemp[p<<1]*EvaluateTemp[p<<1|1];
	}
	void EvaluateSolve2(Poly &res,Poly F,int l,int r,int p=1){
		if(l==r){ res[l]=F[0]; return; }
		int mid=(l+r)>>1;
		EvaluateSolve2(res,F%EvaluateTemp[p<<1],l,mid,p<<1);
		EvaluateSolve2(res,F%EvaluateTemp[p<<1|1],mid+1,r,p<<1|1);
	}
	Poly Evaluate(Poly a,Poly b,int flag=1){ // 多项式多点求值
		Poly res(b.size());
		if(flag) EvaluateSolve1(b,0,b.size()-1);
		EvaluateSolve2(res,a,0,b.size()-1);
		return res;
	}
	Poly InterpolationSolve(Poly &T,int l,int r,int p=1){ 
		if(l==r) return Poly{T[l]};
		int mid=(l+r)>>1;
		return InterpolationSolve(T,l,mid,p<<1)*EvaluateTemp[p<<1|1]+InterpolationSolve(T,mid+1,r,p<<1|1)*EvaluateTemp[p<<1];
	}
	Poly Interpolation(Poly X,Poly Y){ // 多项式快速插值
		int n=X.size();
		EvaluateSolve1(X,0,n-1);
		Poly T=Evaluate(Deri(EvaluateTemp[1]),X,0);
		rep(i,0,n-1) T[i]=Y[i]*qpow(T[i])%P;
		return InterpolationSolve(T,0,n-1);
	}

	void FFPTrans(Poly &a,int f){ // FFP<->EGF
		int n=a.size();
		Poly b(n);
		if(f==1) rep(i,0,n-1) b[i]=FInv[i];
		else rep(i,0,n-1) b[i]=(i&1)?P-FInv[i]:FInv[i];
		a=a*b; a.resize(n);
	}
	Poly FFPMul(Poly a,Poly b){ // FFP卷积
		int n=a.size()+b.size()-1;
		a.resize(n),b.resize(n);
		FFPTrans(a,1),FFPTrans(b,1);
		rep(i,0,n-1) a[i]=1ll*a[i]*b[i]%P*Fac[i]%P;
		FFPTrans(a,-1);
		return a;
	}
	Poly PolyToFFP(Poly F){ // 多项式转FFP
		int n=F.size();
		Poly G(n);
		rep(i,0,n-1) G[i]=i;
		G=Evaluate(F,G);
		rep(i,0,n-1) F[i]=1ll*G[i]*FInv[i]%P;
		FFPTrans(F,-1);
		return F;
	}
	Poly FFPToPoly(Poly F){ // FFP转多项式
		FFPTrans(F,1);
		int n=F.size(); Poly X(n);
		rep(i,0,n-1) X[i]=i,F[i]=1ll*F[i]*Fac[i]%P;
		EvaluateSolve1(X,0,n-1);
		rep(i,0,n-1) {
			F[i]=1ll*F[i]*FInv[i]%P*FInv[n-i-1]%P;
			if((n-i-1)&1) F[i]=(P-F[i])%P;
		}
		return InterpolationSolve(F,0,n-1);
	}
}
using namespace Polynomial;


int main(){
	int n=rd();
	Init_w();
	Poly F(n);
	rep(i,0,n-1) F[i]=rd();
	Show(PolyToFFP(F));
}

$$\$$ $$\$$ $$\$$