$\text{Link}$

题意

对 $1\le i\le m$ 求满足所有节点权值在集合 $\{c_i|1\le i\le n\}$ 中的有根二叉树个数。其中一节点的权值为其子树中所有节点的权值和。

$1\le n,m,c_i\le10^5$.

思路

这题是一道生成函数入门题。

首先想一个 $\text{dp}$，设 $f_i$ 表示权值为 $i$ 的答案，$g_i=[i\in\{c_i\}]$。

$$f_n=[n=0]+\sum_{i\ge1}g_i\sum_{j=1}^{n-i}f_jf_{n-i-j}$$

写出 $f$ 的 $\text{OGF}$，

$$F(x)=\sum_{n\ge0}f_nx^n$$ $$F(x)=1+\sum_{n\ge0}\sum_{i\ge1}g_i\sum_{j=1}^{n-i}f_jf_{n-i-j}x^n$$$$F(x)=1+G(x)F^2(x)$$ $$G(x)F^2(x)-F(x)+1=0$$

可以解得

$$F(x)=\dfrac{-b\pm\sqrt{b^2-4ac}}{2a}=\dfrac{1\pm\sqrt{1-4G(x)}}{2G(x)}$$

有两解，于是可以将式子化为

$$2F(x)G(x)=1\pm\sqrt{1-4G(x)}$$

此时若取 $+$ 号，有

$$[x^0]2F(x)G(x)=0,[x^0]1+\sqrt{1-4G(x)}\ne0$$

即

$$2F(x)G(x)\ne1+\sqrt{1-4G(x)}$$

故取 $-$ 号。

$$F(x)=\dfrac{1-\sqrt{1-4G(x)}}{2G(x)}$$

$[x^0]G(x)=0$，无法对 $G(x)$ 求逆，考虑上下同乘 $1+\sqrt{1-4G(x)}$，

$$F(x)=\dfrac{4G(x)}{2G(x)+2G(x)\sqrt{1-4G(x)}}$$ $$F(x)=\dfrac{2}{1+\sqrt{1-4G(x)}}$$

接下来就可以直接开根+求逆了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int mod=998244353,inv2=mod+1>>1,N=262145+10;
namespace Poly{
	int a[N],b[N],c[N],rev[N],f[N],g[N],inv[N],fac[N],ifac[N],lim;
	inline void init(int n,int mode=1){
		if(mode){
			int l=0;
			for(lim=1;lim<=n;lim<<=1)l++;
			for(int i=1;i<lim;i++){
				rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
			}
		}else{
			for(lim=1;lim<=n;lim<<=1);
		}
	}
	inline int qpow(int x,int y){
		int res=1;
		while(y){
			if(y&1) res=1ll*res*x%mod;
			x=1ll*x*x%mod;
			y>>=1;
		}
		return res;
	}
	inline void Prefix(int n){
		inv[1]=1;
		for(int i=2;i<=n;i++)
			inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fac[0]=1;
		for(int i=1;i<=n;i++)
			fac[i]=1ll*fac[i-1]*i%mod;
		ifac[n]=qpow(fac[n],mod-2);
		for(int i=n;i>=1;i--)
			ifac[i-1]=1ll*ifac[i]*i%mod;
	}
	inline void NTT(int *a,int t){
		for(int i=0;i<lim;i++)
			if(i<rev[i])
				swap(a[i],a[rev[i]]);
		for(int i=1;i<lim;i<<=1){
			int gl=qpow(3,(mod-1)/(i<<1));
			for(int j=0;j<lim;j+=(i<<1)){
				int t1,t2,now=1;
				for(int k=0;k<i;k++,now=1ll*now*gl%mod){
					t1=a[j+k];
					t2=1ll*now*a[i+j+k]%mod;
					a[j+k]=(t1+t2)%mod;
					a[i+j+k]=(t1-t2+mod)%mod;
				}
			}
		}
		if(t==1) return ;
		int Inv=qpow(lim,mod-2);
		reverse(a+1,a+lim);
		for(int i=0;i<lim;i++)
			a[i]=1ll*a[i]*Inv%mod;
	}
	inline void Inv(int *a,int *b,int n){
		if(n==1){
			b[0]=qpow(a[0],mod-2);
			return ;
		}
		Inv(a,b,n+1>>1);
		init(n<<1);
		for(int i=0;i<n;i++)
			c[i]=a[i];
		for(int i=n;i<lim;i++)
			c[i]=0;
		NTT(c,1),NTT(b,1);
		for(int i=0;i<lim;i++)
			b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
		NTT(b,-1);
		for(int i=n;i<lim;i++)
			b[i]=0;
	}
	inline void Mul(int *f,int *g,int *h,int n){
		static int a[N],b[N];
		init(n<<1);
		memset(a,0,lim<<2);
		memcpy(a,f,n<<2);
		memset(b,0,lim<<2);
		memcpy(b,g,n<<2);
		NTT(a,1),NTT(b,1);
		for(int i=0;i<lim;i++){
			h[i]=1ll*a[i]*b[i]%mod;
		}
		NTT(h,-1);
	}
	inline void Sqrt(int *f,int *g,int n){
		if(n==1){ g[0]=1;return ; }
		Sqrt(f,g,n+1>>1);
		memset(a,0,n<<2);
		Inv(g,a,n);
		Mul(f,a,a,n);
		for(int i=0;i<n;i++)
			g[i]=1ll*(g[i]+a[i])*inv2%mod;
	} 
}
using namespace Poly;
int n,m,mx;
int main(){
	n=read(),m=read()+1;
	for(int i=0;i<n;i++){
		int x=read();
		g[x]++;
		mx=max(mx,x);
	}
	mx++;
	for(int i=1;i<mx;i++)
		if(g[i])
			g[i]=mod-4*g[i];
	g[0]++;
	Sqrt(g,b,m);
	b[0]++;
	Inv(b,f,m);
	for(int i=1;i<m;i++)
		write(f[i]*2%mod),putc('\n');
	flush();
}

再见 qwq~