多项式基础知识（2）

（一）多项式求逆

给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$， 满足 $F(x) * G(x) \equiv 1 \pmod{x^n}$。系数对 $998244353$ 取模。
$1 \leq n \leq 10^5$，$0 \leq a_i \leq 10^9$。

设原多项式为$A$，模$x^n$的逆元为$B$，模$x^{\lceil\frac{n}2\rceil}$逆元为$B'$,则可得:

$A*B'\equiv 1\ (mod \ x^{\lceil\frac{n}2\rceil})\ \ \ \text{\textcircled 1}$

$A*B \equiv 1\ (mod \ x^{\lceil\frac{n}2\rceil})\ \ \ \text{\textcircled 2}$

两式相减得：$B'-B\equiv 0\ (mod\ x^{\lceil\frac{n}2\rceil})$

两边平方得：$B'^2+B^2-2B'B\equiv0\ (mod\ x^n)$

两边同时乘以$A$，并由$\text{\textcircled 1}$和$\text{\textcircled 2}$两式得：

$AB'^2+B-2B'\equiv0\ (mod\ x^n)$

移项得：$B\equiv2B'-AB'^2\ (mod\ x^n)$

则可以从$B(0)$利用多项式乘法来递推得到$B$，且$B(0)=A(0)^{-1}$

（二）多项式除法

给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$ ，请求出多项式 $Q(x)$, $R(x)$，满足以下条件：

• $Q(x)$ 次数为 $n-m$，$R(x)$ 次数小于 $m$
• $F(x) = Q(x) * G(x) + R(x)$
  所有的运算在模 $998244353$ 意义下进行。

前置知识：$NTT$，多项式求逆
定义$F_R(x)$为$F(x)$系数翻转后的函数，令$F(x)$的次数为$k$，则：
$F_R(x)=F(\frac{1}x)*x^k$

若$f(x)=g(x)*q(x)+r(x)$，$f$的次数为$n$，$g$的次数为$m$，$q$的次数为$n-m$，$r$的次数为$m-1$，把$\frac{1}x$带入得：

$f(\frac{1}x)=g(\frac{1}x)*q(\frac{1}x)+r(\frac{1}x)$

两边同时乘以$x^n$得：

$f(\frac{1}x)*x^n=g(\frac{1}x)*x^m*q(\frac{1}x)*x^{n-m}+r(x)*x^n$

$f_R(x)=g_R(x)*q_R(x)+r_R(x)*x^{n-m+1}$

$f_R(x)\equiv g_R(x)*q_R(x)\ (mod\ x^{n-m+1})$

$q_R(x)\equiv \frac{f_R(x)}{g_R(x)}\ (mod\ x^{n-m+1})$

由于$f_R(x)$和$g_R(x)$均为题目中已知，可以先求出$g_R(x)$的逆，然后进行多项式乘法可求出$q_R(x)$，从而带入原式求出$r(x)$。

（三）多项式开根

给定一个 $n-1$ 次多项式 $A(x)$，求一个在 ${} \bmod x^n$ 意义下的多项式 $B(x)$，使得 $B^2(x) \equiv A(x) \pmod{x^n}$。若有多解，请取零次项系数较小的作为答案。
多项式的系数在 ${}\bmod 998244353$ 的意义下进行运算。
保证 $a_0 = 1$。输出 $n$ 个整数，表示答案多项式的系数 $b_0, b_1, \dots, b_{n-1}$。
$1 \le n \leq 10^5$，$0 \le a_i < 998244353$。

前置知识：多项式求逆

设$B'^2(x)\equiv A(x)(mod\ x^{\lceil\frac{n}2\rceil})$

又由$B^2(x)\equiv A(x)(mod\ x^n)$

两式相减得：
$B^2(x)-B'^2(x)\equiv 0(mod\ x^{\lceil\frac{n}2\rceil})$

两边进行平方得：
$B^4(x)+B'^4(x)-2B^2(x)B'^2(x)\equiv0(mod\ x^n)$

则：$B^4(x)+B'^4(x)+2B^2(x)B'^2(x)\equiv 4B^2(x)B'^2(x)(mod\ x^n)$

两边同时开根号得：

$B^2(x)+B'^2(x)\equiv 2B(x)B'(x)(mod\ x^n)$

要注意此处为模$x^n$，而不是$x^{\lceil\frac{n}2\rceil}$

$A(x)+B'^2(x)\equiv 2B(x)B'(x)$

$B(x)\equiv \frac{A(x)+B'^2(x)}{2B'(x)}$

利用多项式求逆和多项式乘法即可求得$B(x)$
其中$B(0)=\sqrt{A(0)}$，即$B(0)$为$A(0)$的二次剩余.

插话：其实多项式求逆和多项式开根的核心思想一样，都是通过变形来构造出递推的形式
时间复杂度为$O(nlog{n})$

（四）多项式求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}$.保证 $a_0 = 1$.$n \le 10^5$.

将$B(x)= ln{A(x)}$两边对$x$求导得：

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

只需对$A(x)$求导，然后求逆，最后多项式乘法即可求出$B'(x)$，最后用积分求出$B(x)$.

（五）多项式求exp

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

令$F(x)=e^{A(x)}$，对两边取$ln$得：$\ln{F(x)}-A(x)=0$

设$G(F(x))=\ln{F(x)}-A(x)$，即求$G(F(x))$的零点，可以用牛顿迭代法来解决.

$G'(F(x))=\frac{1}{F(x)}$，要注意此时$F(x)$为自变量，虽然$A(x)$中含有$x$，但此时$A(x)$仍可看为常数.

带入牛顿迭代公式得：

$F(x)\equiv F_0(x)(1-\ln{F_0(x)}+A(x))\ (mod\ x^n)$

其中$F_0(x)$为$F(x)$模$x^{\lceil\frac{n}2\rceil}$下的值.

又由$A(0)=0$,则$F(x)\equiv 1(mod\ x)$.

只需利用多项式求$ln$和多项式乘法即可递推求解$F(x)$.

（六）多项式快速幂

给定一个 $n-1$ 次多项式 $A(x)$，求一个在 $\bmod\ x^n$ 意义下的多项式 $B(x)$，使得 $B(x) \equiv (A(x))^k \ (\bmod\ x^n)$。
多项式的系数在 $\bmod\ 998244353$ 的意义下进行运算。
$1 < n \leq 10^5$，$0 < k \leq 10^{10^5}$，$a_i \in [0,998244352]$，$a_0=1$。

对原式变形得：$B(x)\equiv e^{k\ln{A(x)}}$

我们可以先对$A(x)$求$ln$，然后乘以$k$，最后再进行多项式$exp$，时间复杂度为$O(nlogn)$.

（七）生成函数

由于多项式的题目经常与生成函数联系起来，故在此处介绍一下生成函数.

1.普通生成函数（$OGF$）幂级数形式为：
$F(x)=\sum_{n}a_nx^n$

2.指数生成函数（$EGF$）幂级数形式为：
$F(x)=\sum_{n}a_n\frac{x^n}{n!}$

一般情况下，带标号的计数问题一般使用$EGF$，无编号的计数问题一般使用$OGF$.

关于多项式常用的模板：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=(1<<21)+20;
const int mod=998244353;
typedef vector<int> vec;

inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline void inc(int &x,int y){x=add(x,y);}
inline void rec(int &x,int y){x=dec(x,y);}
inline int ksm(int x,int y){
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
	return ret; 
}
 
namespace IO {
	inline char nc(){
//		return getchar();
		static char buf[500005],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,500000,stdin),p1==p2)?EOF:*p1++;
	}
	char out[500005],*pout=out,*eout=out+500000;
	inline void flush() { fwrite(out,1,pout-out,stdout),pout=out; }
	inline void pc(char c) { pout==eout&&(fwrite(out,1,500000,stdout),pout=out); (*pout++)=c; }
	template<typename T> inline void put(T x,char suf) {
		static char stk[65];int top=0; while(x) stk[top++]=x%10,x/=10;
		!top?pc('0'),0:0; while(top--) pc(stk[top]+'0'); pc(suf);
	}
	inline int read(){
		char ch=nc(); int sum=0; for(;ch<'0'||ch>'9';ch=nc());
		while(ch>='0'&&ch<='9')sum=(sum<<1)+(sum<<3)+ch-48,ch=nc();
		return sum;
	}
}
#define Rint IO::read()
using IO::put;
using IO::nc;
namespace Prep{
	int Wn[N<<1],lg[N],p2,mx=1,r[N],tot;
	inline void init_poly(int n){
		int p=1;while(p<=n)p<<=1;
		for(int i=2;i<=p;++i) lg[i]=lg[i>>1]+1;
		for(int i=1;i<p;i<<=1){
			int wn=ksm(3,(mod-1)/(i<<1));
			Wn[++tot]=1;
			for(int j=1;j<i;++j) ++tot,Wn[tot]=1ll*Wn[tot-1]*wn%mod;
		}
	}
	inline void init(int lim){
//		cout<<"init"<<lim<<endl;
		int len=lg[lim]-1;
		for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len);
	}
	int iv[N],tp;
	inline void init_inv(int n){
		if(!tp){tp=2;iv[0]=iv[1]=1;}
		for(;tp<=n;++tp) iv[tp]=1ll*(mod-mod/tp)*iv[mod%tp]%mod;
	}
}
using namespace Prep;
 
namespace Cipolla{
	int I,fl=0;
	mt19937 rnd(time(0));
	struct pt{
		int a,b;
		pt(int _a=0,int _b=0){a=_a;b=_b;}
	};
	inline pt operator *(pt x,pt y){
		pt ret;
		ret.a=add(1ll*x.a*y.a%mod,1ll*x.b*y.b%mod*I%mod);
		ret.b=add(1ll*x.a*y.b%mod,1ll*x.b*y.a%mod);
		return ret;
	}
	inline bool check(int x){
		return ksm(x,(mod-1)/2)==1;
	}
	inline int random(){return rnd()%mod;}
	inline pt qpow(pt a,int b){
		pt ret=pt(1,0);
		for(;b;a=a*a,b>>=1) if(b&1) ret=ret*a;
		return ret;
	}
	inline int cipolla(int n){
		if(!check(n)) return 0;
		int a=random();
		while(!a||check(dec(1ll*a*a%mod,n))) a=random();
		I=dec(1ll*a*a%mod,n);
		int ans=qpow(pt(a,1),(mod+1)/2).a;
		return min(ans,(int)mod-ans);
	}
}
using namespace Cipolla;
 
int ddddd=0;
bool flag=0;
namespace Poly{
	struct poly{
		vec v;
		
		inline poly(int w=0):v(1){v[0]=w;}
		inline poly(const vec&w):v(w){}
		
		inline int operator [](int x)const{return x>=v.size()?0:v[x];}
		inline int& operator [](int x){
			if(x>=v.size()) v.resize(x+1);
			return v[x];
		}
		inline int size(){return v.size();}
		inline void resize(int x){v.resize(x);}
		inline void read(int n){v.resize(n);for(int i=0;i<n;++i) v[i]=Rint;}
		inline void print(int n)const{for(int i=0;i<n-1;++i) put(operator[](i),' ');put(operator[](n-1),'\n');}
		
		inline poly slice(int len)const{
			if(len<=v.size()) return vec(v.begin(),v.begin()+len);
			vec ret(v);ret.resize(len);
			return ret;
		}
		
		inline poly operator *(const int &x)const{
			poly ret(v);
			for(int i=0;i<v.size();++i) ret[i]=1ll*ret[i]*x%mod; 
			return ret;
		}
		inline poly operator -()const{
			poly ret(v);
			for(int i=0;i<v.size();++i) ret[i]=dec(0,ret[i]);
			return ret;
		}
		
		inline poly operator*(const poly &g)const;
		inline poly operator/(const poly &g)const;
		inline poly operator%(const poly &g)const;
		inline poly der()const{
			vec ret(v);
			for(int i=0;i<ret.size()-1;++i) ret[i]=1ll*ret[i+1]*(i+1)%mod;
			ret.pop_back();
			return ret; 
		}
		inline poly jifen()const{
			vec ret(v);
			init_inv(ret.size());ret.push_back(0);
			for(int i=ret.size()-1;i;--i) ret[i]=1ll*ret[i-1]*iv[i]%mod;ret[0]=0;
			return ret;
		}
		inline poly rev()const{
			vec ret(v);
			reverse(ret.begin(),ret.end());
			return ret;
		}
		
		inline poly inv()const;
		inline poly div(const poly &FF)const;
		inline poly ln()const;
		inline poly exp()const;
		inline poly pow(int k)const;
		inline poly sqrt()const;
		inline poly mulT(const poly &g,int siz,int tp)const;
	};
	
	inline poly operator +(const poly &x,const poly &y){
		vec v(max(x.v.size(),y.v.size()));
		for(int i=0;i<v.size();++i) v[i]=add(x[i],y[i]);
		return v;
	}
	inline poly operator -(const poly &x,const poly &y){
		vec v(max(x.v.size(),y.v.size()));
		for(int i=0;i<v.size();++i) v[i]=dec(x[i],y[i]);
		return v;
	}
	
	ull fr[N];
	const ull Mod=998244353;
	inline void NTT(poly& f,int lim,int tp){
//		ddddd+=lim*__builtin_ctz(lim);
		for(int i=0;i<lim;++i) fr[i]=f[r[i]];
		for(int mid=1;mid<lim;mid<<=1){
			for(int len=mid<<1,l=0;l+len-1<lim;l+=len){
				for(int k=l;k<l+mid;++k){
					ull w1=fr[k],w2=fr[k+mid]*Wn[mid+k-l]%Mod;
					fr[k]=w1+w2;fr[k+mid]=w1+Mod-w2; 
				}
			}
		}
		for(int i=0;i<lim;++i) fr[i]>=Mod?fr[i]%=Mod:0;
		if(!tp){
			reverse(fr+1,fr+lim);
			int iv=ksm(lim,mod-2);
			for(int i=0;i<lim;++i) fr[i]=fr[i]*iv%mod;
		}
		for(int i=0;i<lim;++i) f[i]=fr[i];
	}
	
	inline poly poly::operator *(const poly &G)const{
		poly f(v),g=G;
		int rec=f.size()+g.size()-1,d=max(f.size(),g.size());
		int len=lg[rec],lim=1<<len+1;
		init(lim);
		NTT(f,lim,1);NTT(g,lim,1);
		for(int i=0;i<lim;++i) f[i]=1ll*f[i]*g[i]%mod;
		NTT(f,lim,0);
		return f.slice(rec);
	}
	
	inline poly poly::inv()const{
		poly g,g0,d;
		g[0]=ksm(v[0],mod-2);
		for(int lim=2;(lim>>1)<v.size();lim<<=1){
			g0=g;d=slice(lim);
			init(lim);
			NTT(g0,lim,1);NTT(d,lim,1);
			for(int i=0;i<lim;++i) d[i]=1ll*g0[i]*d[i]%mod;
			NTT(d,lim,0);
			fill(d.v.begin(),d.v.begin()+(lim>>1),0);
			NTT(d,lim,1);
			for(int i=0;i<lim;++i) d[i]=1ll*d[i]*g0[i]%mod;
			NTT(d,lim,0);
			for(int i=lim>>1;i<lim;++i) g[i]=dec(g[i],d[i]);
		}
		return g.slice(v.size());
	}//10E(n)
	
	inline poly poly::div(const poly &FF)const{
		if(v.size()==1) return 1ll*v[0]*ksm(FF[0],mod-2)%mod;	
		int len=lg[v.size()],lim=1<<len+1,nlim=lim>>1;
		poly F=FF,G0=FF.slice(nlim);	
		G0=G0.inv();
		poly H0=slice(nlim),Q0;
		
		init(lim);
		NTT(G0,lim,1);NTT(H0,lim,1);
		for(int i=0;i<lim;++i) Q0[i]=1ll*G0[i]*H0[i]%mod;
		NTT(Q0,lim,0);Q0.resize(nlim);
		
		poly ret=Q0;
		NTT(Q0,lim,1);NTT(F,lim,1);
		for(int i=0;i<lim;++i) Q0[i]=1ll*Q0[i]*F[i]%mod;
		NTT(Q0,lim,0);
		fill(Q0.v.begin(),Q0.v.begin()+nlim,0);
		for(int i=nlim;i<lim&&i<v.size();++i) Q0[i]=dec(Q0[i],v[i]);
		NTT(Q0,lim,1);
		for(int i=0;i<lim;++i) Q0[i]=1ll*Q0[i]*G0[i]%mod;
		NTT(Q0,lim,0);
		for(int i=nlim;i<lim;++i) ret[i]=dec(ret[i],Q0[i]); 
		return ret.slice(v.size());
	}
	
	inline poly poly::ln()const{
		return der().div(*this).jifen(); 
	}//13E
	
	namespace EXP{
		const int logB=4;
		const int B=16;
		poly f,ret,g[30][B];
		inline void exp(int lim,int l,int r){
//			cout<<lim<<" "<<l<<" "<<r<<endl;
			if(r-l<=64){
				for(int i=l;i<r;++i){
					ret[i]=(!i)?1:1ll*ret[i]*iv[i]%mod;
					for(int j=i+1;j<r;++j) inc(ret[j],1ll*ret[i]*f[j-i]%mod);
				}
				return ;
			}
			int k=(r-l)/B;
			poly bl[B];
			for(int i=0;i<B;++i) bl[i].resize(k<<1);
			int len=1<<lim-logB+1;
			for(int i=0;i<B;++i){
				if(i>0){
					init(len);NTT(bl[i],len,0);
					for(int j=0;j<k;++j)
						inc(ret[l+i*k+j],bl[i][j+k]);
				}
				exp(lim-logB,l+i*k,l+(i+1)*k);
				if(i<B-1){
					poly H;H.resize(k<<1);
					for(int j=0;j<k;++j) H[j]=ret[j+l+i*k];
					init(len);NTT(H,len,1);
					for(int j=i+1;j<B;++j)
						for(int t=0;t<(k<<1);++t) inc(bl[j][t],1ll*H[t]*g[lim][j-i-1][t]%mod); 
				}
			}
		}
		inline void init_exp(){
			ret.resize(f.size());
			for(int i=0;i<f.size();++i) f[i]=1ll*f[i]*i%mod,ret[i]=0;
			int mx=lg[f.size()]+1;
			init_inv(1<<mx);
			for(int lim=mx;lim>=logB;lim-=logB){
				int bl=1<<(lim-logB),tot=0,ll=1<<(lim-logB+1);
				init(ll);
				for(int i=0;i<B-1;++i){
					g[lim][i].resize(bl<<1);
					for(int j=0;j<(bl<<1);++j) g[lim][i][j]=f[j+bl*i];
					NTT(g[lim][i],ll,1);
				}
			}
		}
	}
	
	inline poly poly::exp()const{
		EXP::f=*this;
		EXP::init_exp();
		EXP::exp(lg[v.size()]+1,0,1<<lg[v.size()]+1);
		return EXP::ret.slice(v.size());
	}
	
	
	inline poly poly::pow(int k)const{
		return ((*this).ln()*k).exp();
	}
	
	inline poly poly::operator /(const poly &Q)const{
		if(v.size()<Q.v.size()) return 0;
		int p=v.size()-Q.v.size()+1;
		poly fr=rev(),qr=Q.rev();
		fr.resize(p);qr.resize(p);
		return fr.div(qr).rev();
	} 
	inline poly poly::operator %(const poly &Q)const{
		poly F(v);
		return 	(F-(Q*(F/Q))).slice(Q.v.size()-1);
	} 
	inline poly poly::sqrt()const{
		poly g,h,gf,F1,F2,F3,f(v);
		g[0]=cipolla(operator[](0));
		h[0]=ksm(g[0],mod-2);
		gf[0]=g[0];gf[1]=g[0];
		int iv=(mod+1)/2; 
		init(1);
		for(int lim=1;lim<v.size();lim<<=1){
			for(int i=0;i<lim;++i) F1[i]=1ll*gf[i]*gf[i]%mod;
			NTT(F1,lim,0);
			for(int i=0;i<lim;++i) F1[i+lim]=dec(F1[i],f[i]),F1[i]=0;
				
			int nlim=lim<<1;init(nlim);
			for(int i=lim;i<nlim;++i) rec(F1[i],f[i]);
			F2=h;F2.resize(lim);
			NTT(F1,nlim,1);NTT(F2,nlim,1);
			
			for(int i=0;i<nlim;++i) F1[i]=1ll*F1[i]*F2[i]%mod;
			NTT(F1,nlim,0);
			for(int i=lim;i<nlim;++i) g[i]=dec(0,1ll*F1[i]*iv%mod); 
			
			if(nlim<v.size()){
				gf=g;
				NTT(gf,nlim,1);
				for(int i=0;i<nlim;++i) F3[i]=1ll*gf[i]*F2[i]%mod;
				NTT(F3,nlim,0);
				fill(F3.v.begin(),F3.v.begin()+lim,0);
				NTT(F3,nlim,1);
				for(int i=0;i<nlim;++i) F3[i]=1ll*F3[i]*F2[i]%mod;
				NTT(F3,nlim,0);
				for(int i=lim;i<nlim;++i) rec(h[i],F3[i]);
			}
		}
		return g.slice(v.size());
	}
	inline poly poly::mulT(const poly &G,int siz,int tp)const{
		poly f(v),g=G;
		if(f.size()<=100){
			poly ret;
			for(int i=0;i<f.size();++i){
				int fr=0;
				if(tp==1) fr=max(fr,i-(int)(f.size()-g.size()));
				for(int j=fr;j<=i&&j<g.size();++j) inc(ret[i-j],1ll*f[i]*g[j]%mod);
			} 
			return ret;
		}
		int len=lg[f.size()*tp],lim=1<<len+1,gg=g.size();
		init(lim);
		reverse(g.v.begin(),g.v.end());
		NTT(f,lim,1);NTT(g,lim,1);
		for(int i=0;i<lim;++i) f[i]=1ll*f[i]*g[i]%mod;
		NTT(f,lim,0);
		return vec(f.v.begin()+gg-1,f.v.begin()+gg+siz-1);
	}
}
using namespace Poly;
 
inline int sread(){
	long long m=mod,x=0;char ch=nc();
	while(!isdigit(ch)){ch=nc();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);x%=m;ch=nc();}
	return x;
}
//remember to init_poly(多项式最高可能次数) 
int n,k;poly f;
/*
int main(){
//	freopen("poly2.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=Rint+1,k=Rint;
	f.read(n);
	init_poly(n<<1);
	poly g=f+poly(2)-poly(f[0]);
	g=g-(f.sqrt().inv().jifen().exp());
	(g.ln()+poly(1)).pow(k).der().print(n-1);
	IO::flush(); 
	return 0;
}
*/
int main(){
	n=Rint;
	f.read(n);
	init_poly(n*2);
	f.ln().print(n);
	IO::flush();
	return 0;
}