Description：

题目大意：给定 $n$ 和集合 $C$ ，对于 $i=1\sim n$ 求多少 $i$ 个节点有标号的多叉树满足： 1.父亲节点的标号大于子节点 。

2.一个点如果有儿子，则有两个无序的 $a$ 型儿子，有 $c$ 个无序的 $b$ 型儿子，其中 $c\in C$ 。

3.如果一个点是根节点或 $a$ 型儿子，那么它可以有儿子或者是一个叶节点；如果一个点是ββ型儿子，那么它只能是一个叶节点。

$1\leqslant n\leqslant 200000$

Solution：

设答案为 $f(n)$ ，那么显然有转移： $$ f(n)=\frac 1 2\sum_{l=1}^{n-1}\sum_{r=1}^{n-1-l}f(l)\times f(r)\times\binom{n-1}{n-1-l-r}\binom{l+r}{l}[n-1-l-r\in C] $$ 那么我们可以把组合数拆开： $$ f(n)=\frac 1 2(n-1)!\sum_{l=1}^{n-1}\sum_{r=1}^{n-1-l}\frac{f(l)}{l!}\times \frac{f(r)}{r!}\times\frac{[n-1-l-r\in C]}{(n-1-l-r)!} $$ 这显然是三个函数的卷积，除二是因为两个子树相同。

另一种方法是利用指数型生成函数，之所以使用指数型生成函数是因为计数对象有标号： $$ F(x)=\sum_{i=0}f(i)\frac{x^i}{i!} $$ 但是实际上根节点编号一定是 $1$ ，因此根节点实际上不参与计数： $$ F(x)=\sum_{i=0}f(i)\frac{x^{i-1}}{(i-1)!} $$ 那么类似的可以得到方程： $$ F=\frac 1 2F^2C+1 $$ 和上面是一样的。

然后有三种做法，一是用上面那个方程直接牛顿迭代，二是用上面那个方程直接多项式开方，三是用上面那个递推式分治 $FFT$ 。

这里写的是分治 $+NTT$ ，但是需要写成： $$ \begin{align} g(x)&=\sum_{i=0}^xf(i)f(x-i)\\ f(x)&=\sum_{i=0}^xC(i)\times g(x-i)\\ C(i)&=[i\in C]\frac 1{2\times i!} \end{align} $$ 然后这个就可以分治 $FFT$ 了，因为首先用 $g$ 求 $f$ 是肯定可以分治 $FFT$ 的，也就是考虑左边的 $g$ 对右边的 $f$ 的贡献，但是还要求 $g$ ，由于 $g$ 等于 $f$ 卷自己，也就是说分治右半边的 $f$ 还没求出来，那么我们就要计算卷积中 $x$ 和 $i-x$ 都 $\leqslant mid$ 的部分对右边的贡献，别的可以等到之后再计算，首先先设 $a[i]=g[i-l](i\in[l,mid])$ ，然后考虑 $b$ 是什么，显然对于 $i<l$ 的，应该计算两次，但是只计算了一次，那么他还要有一个 $2$ 的系数，对于 $[l,mid]$ 的，在卷积中已经计算了两次，因此系数不变。

Code：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

#define MAXN 1200010

bool get()

{

	char c = getchar();

	while(!isdigit(c))c = getchar();

	return (c == '1');

}

ll c[MAXN];

#define P 998244353

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % P;

		a = a * a % P;

		b = b >> 1;

	}

	return res;

}

namespace poly

{

	int rev[MAXN];

	ll ww[MAXN << 1],*g = ww + MAXN;

	void NTT(ll f[],int l,int type)

	{

		for(int i = 0;i < l;++i)

		{

			if(i < rev[i])swap(f[i],f[rev[i]]);

		}

		for(int i = 2;i <= l;i = i << 1)

		{

			ll wn = g[type * l / i];

			for(int j = 0;j < l;j += i)

			{

				ll w = 1;

				for(int k = j;k < j + i / 2;++k)

				{

					ll u = f[k],t = w * f[k + i / 2] % P;

					f[k] = (u + t) % P;

					f[k + i / 2] = (u - t + P) % P;

					w = w * wn % P;

				}

			}

		}

		if(type == -1)

		{

			ll ni = power(l,P - 2);

			for(int i = 0;i < l;++i)f[i] = f[i] * ni % P;

		}

		return;

	}

	void mul(ll a[],ll b[],ll res[],int deg)

	{//cout << " : " << endl;

		//for(int i = 0;i < deg;++i)cout << a[i] << " ";cout << endl;

		//for(int i = 0;i < deg;++i)cout << b[i] << " ";cout << endl;

		int l = 0,len = 1;

		for(;len <= (deg << 1);len = len << 1)++l;

		g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

		for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

		for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

		NTT(a,len,1);NTT(b,len,1);

		for(int i = 0;i < len;++i)res[i] = a[i] * b[i] % P;

		NTT(res,len,-1);

		for(int i = 0;i < len;++i)a[i] = b[i] = 0;

		//for(int i = 0;i < len;++i)cout << res[i] << " ";cout << endl;

		return;

	}

}

ll f[MAXN],g[MAXN];

ll fac[MAXN],inv[MAXN];

ll tmp1[MAXN],tmp2[MAXN],tmp3[MAXN],res[MAXN];

void solve(int l,int r)

{

	if(l == r)

	{

		f[l] = f[l] * fac[l - 1] % P;

		return;

	}

	int mid = ((l + r) >> 1);

	solve(l,mid);

	for(int i = l;i <= mid;++i)tmp1[i - l] = g[i];

	int d = r - l + 1;

	for(int i = 0;i < r - l + 1;++i)tmp2[i] = c[i];

	poly::mul(tmp1,tmp2,res,d + 1);

	for(int i = mid + 1;i <= r;++i)f[i] = (f[i] + res[i - l - 1]) % P;

	for(int i = l;i <= mid;++i)tmp1[i - l] = f[i] * inv[i] % P;

	for(int i = 0;i <= r - l;++i)

	{

		if(i < l)tmp2[i] = f[i] * inv[i] * 2 % P;

		else if(i <= mid)tmp2[i] = f[i] * inv[i] % P;

	}

	poly::mul(tmp1,tmp2,res,d + 1);

	for(int i = mid + 1;i <= r;++i)g[i] = (g[i] + res[i - l]) % P;

	solve(mid + 1,r);

	return;

}

int main()

{

	scanf("%d",&n);

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % P;

	inv[n] = power(fac[n],P - 2);

	for(int i = n - 1;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % P;

	for(int i = 0;i < n;++i)if(get())c[i] = inv[i] * inv[2] % P;

	f[1] = 1;

	solve(1,n);

	for(int i = 1;i <= n;++i)printf("%lld\n",f[i]);

	return 0;

}