多项式板子

namespace Poly
{
	int rev[N],limit;
	inline void qmo(int &x){x+=(x>>31)&mod;}
	inline int quick_pow(int x,int k){int res=1;for (;k;k>>=1,x=1ll*x*x%mod) if (k&1) res=1ll*res*x%mod;return res;}
	inline void NTT_init(int size)
	{
		int l=0;limit=1;
		while (limit<=size) limit<<=1,l++;
		rep(i,0,limit-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	}
	inline void NTT(int *A,int tp)
	{
		rep(i,0,limit-1) if (i<rev[i]) swap(A[i],A[rev[i]]);
		for (int mid=1;mid<limit;mid<<=1)
		{
			int Wn=quick_pow(tp==1?3:quick_pow(3,mod-2),mod/(mid<<1));
			for (int j=0;j<limit;j+=(mid<<1))
			{
				int w=1;
				rep(k,0,mid-1)
				{
					int x=A[j+k],y=1ll*w*A[j+k+mid]%mod;
					qmo(A[j+k]=x+y-mod);
					qmo(A[j+k+mid]=x-y);
					w=1ll*w*Wn%mod;
				}
			}
		}
		if (tp==-1)
		{
			int I=quick_pow(limit,mod-2);
			rep(i,0,limit-1) A[i]=1ll*A[i]*I%mod;
		}
	}
	inline void PolyInv(int *A,int *F,int n)
	{
		static int tmp[N];
		if (n==1) return void(F[0]=quick_pow(A[0],mod-2));
		int mid=(n+1)>>1; PolyInv(A,F,mid); NTT_init(n<<1);
		rep(i,0,n-1) tmp[i]=A[i]; rep(i,n,limit-1) tmp[i]=0;
		NTT(F,1),NTT(tmp,1);
		rep(i,0,limit-1) F[i]=1ll*F[i]*(2-1ll*F[i]*tmp[i]%mod+mod)%mod;
		NTT(F,-1);
		rep(i,n,limit-1) F[i]=0;
	}
	inline void PolySqrt(int *A,int *F,int n)
	{
		static int tmp1[N],tmp2[N],tmp3[N];
		if (n==1) return void(F[0]=sqrt(A[0])+0.5);
		int mid=(n+1)>>1; PolySqrt(A,F,mid);
		rep(i,0,n-1) tmp1[i]=A[i],tmp2[i]=F[i]; PolyInv(F,tmp3,n);
		NTT_init(n<<1),NTT(tmp1,1),NTT(tmp2,1),NTT(tmp3,1);
		const int inv2=quick_pow(2,mod-2);
		rep(i,0,limit-1) F[i]=1ll*inv2*(1ll*tmp1[i]*tmp3[i]%mod+tmp2[i])%mod;
		NTT(F,-1);
		rep(i,n,limit-1) F[i]=0;
		rep(i,0,limit-1) tmp1[i]=tmp2[i]=tmp3[i]=0;
	}
}