hello,polynomial!

设$f_i$表示权值为$i$的树有多少种，权值集合为$S$，那么$\begin{align*}f_i=1+\sum\limits_{j=0}^i[i-j\in S]\sum\limits_{k=0}^jf_kf_{j-k}\end{align*}$（枚举根节点的权值，再枚举左右儿子的权值，还有仅有一点的情况）

这是一个卷积再卷积，用生成函数处理会很方便，设$\begin{align*}F(x)=\sum\limits_{i=0}^\infty f_ix^i,G(x)=\sum\limits_{i=0}^\infty[i\in S]x^i\end{align*}$，那么$F(x)=G(x)F^2(x)+1$

我们已经知道$G(x)$了，现在要求$F(x)$，上式是关于$F(x)$的一元二次方程，直接解，$F(x)=\dfrac{1\pm\sqrt{1-4G(x)}}{2G(x)}$，因为$G(0)=0,F(0)=0$，所以我们取$F(x)=\dfrac{1-\sqrt{1-4G(x)}}{2G(x)}=\dfrac2{1+\sqrt{1-4G(x)}}$

要对多项式开平方根和除法？

只能说一开始发展多项式全家桶的人是个人才...

多项式求逆：给定$F(x)$，求$G(x)$满足$F(x)G(x)\equiv1\ (\text{mod }x^n)$

我们采用倍增的思想：假设已经求出了$G(x)$使得$F(x)G(x)\equiv1(\text{mod }x^n)$，我们要求$H(x)$使得$F(x)H(x)\equiv1(\text{mod }x^{2n})$

$\begin{align*}F(x)G(x)&\equiv1(\text{mod }x^n)\\F(x)G(x)-1&\equiv0(\text{mod }x^n)\\\left(F(x)G(x)-1\right)^2&\equiv0(\text{mod }x^{2n})\\F^2(x)G^2(x)-2F(x)G(x)+1&\equiv0(\text{mod }x^{2n})\\F(x)G^2(x)-2G(x)+H(x)&\equiv0(\text{mod }x^{2n})\\H(x)&\equiv G(x)\left(2-F(x)G(x)\right)(\text{mod }x^{2n})\end{align*}$

每层用FFT求多项式乘法，总时间复杂度为$T(n)=T\left(\dfrac n2\right)+O(n\log_2n)=O(n\log_2n)$

多项式开根：给定$F(x)$，求$G(x)$满足$G^2(x)\equiv F(x)(\text{mod }x^n)$

倍增：假设已求得$G(x)$使$G^2(x)\equiv F(x)(\text{mod }x^n)$，我们要求$H(x)$使得$H^2(x)\equiv F(x)(\text{mod }x^{2n})$

$\begin{align*}G^2(x)&\equiv F(x)(\text{mod }x^n)\\G^2(x)-F(x)&\equiv0(\text{mod }x^n)\\\left(G^2(x)-F(x)\right)^2&\equiv0(\text{mod }x^{2n})\\\left(G^2(x)+F(x)\right)^2&\equiv4G^2(x)F(x)(\text{mod }x^{2n})\\\left(G^2(x)+F(x)\right)^2&\equiv4G^2(x)H^2(x)(\text{mod }x^{2n})\\G^2(x)+F(x)&\equiv2G(x)H(x)(\text{mod }x^{2n})\\H(x)&\equiv\dfrac12\left(\dfrac{F(x)}{G(x)}+G(x)\right)(\text{mod }x^{2n})\end{align*}$

每层要FFT和多项式求逆，时间复杂度还是$O(n\log_2n)$（毒瘤时间复杂度），只不过常数特别大

注意写多项式相关的时候，没用到的项FFT之前一定要置$0$（不要以为不用到高次系数就可以不管）

然后这题就做完了，还是很愉悦的2333

#include
     
      #include
      
       const int mod=998244353,inv2=499122177;typedef long long ll;int mul(int a,int b){return a*(ll)b%mod;}int ad(int a,int b){return(a+b)%mod;}int de(int a,int b){return(a-b)%mod;}int pow(int a,int b){	int s=1;	while(b){		if(b&1)s=mul(s,a);		a=mul(a,a);		b>>=1;	}	return s;}int rev[300010],N,iN;void swap(int&a,int&b){a^=b^=a^=b;}void pre(int n){	int i,k;	for(N=1,k=0;N
       
        <<=1)k++;	for(i=0;i
        
         >1]>>1)|((i&1)<<(k-1));	iN=pow(N,mod-2);}void ntt(int*a,int on){	int i,j,k,t,w,wn;	for(i=0;i
         
          >1;k++){				t=mul(a[i/2+j+k],w);				a[i/2+j+k]=de(a[j+k],t);				a[j+k]=ad(a[j+k],t);				w=mul(w,wn);			}		}	}	if(on==-1){		for(i=0;i
          
           >1); pre(n<<1); memset(t0,0,sizeof(t0)); for(i=0;i
           
            >1); memset(t2,0,sizeof(t2)); getinv(b,t2,n); ntt(t2,1); memset(t1,0,sizeof(t1)); for(i=0;i