题解 小朋友和二叉树

题目传送门

题目大意

给出集合(S={c_1,c_2,c_3,..,c_m})，求出对于任意(tin[1,m])有多少个二叉树满足所有顶点的权值都在(S)中且权值之和为(t)。

思路

我们设(F)为答案的生成函数，(G)为集合(S)的生成函数。可以得到:

[F=F^2G+1 ]

(F^2)就是枚举左右儿子，(G)就是根节点，加(1)是因为可以是空子树。

得到:

[F=frac{1pm sqrt{1-4G}}{2G} ]

因为如果取正号的话，当(G=0)为零时为正无穷而取负号的话可以用洛必达法则求出来，所以取负号。我们再化简得到:

[F=frac{2}{1+sqrt{1-4G}} ]

于是，我们就在(Theta(mlog m))的时间复杂度内解决了这个问题。

( ext {Code})

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define inv2 499122177
#define ll long long
#define mod 998244353
#define MAXN 400005
#define Gi 3

int quick_pow (int a,int b){
	int res = 1;for (;b;b >>= 1,a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res; 
}

int limit = 1,l,r[MAXN];

void NTT (int *a,int type){
	for (Int i = 0;i < limit;++ i) if (i < r[i]) swap (a[i],a[r[i]]);
	for (Int mid = 1;mid < limit;mid <<= 1){
		int Wn = quick_pow (Gi,(mod - 1) / (mid << 1));
		if (type == -1) Wn = quick_pow (Wn,mod - 2);
		for (Int R = mid << 1,j = 0;j < limit;j += R){
			for (Int k = 0,w = 1;k < mid;++ k,w = 1ll * w * Wn % mod)
			{
				int x = a[j + k],y = 1ll * w * a[j + k + mid] % mod;
				a[j + k] = (x + y) % mod,a[j + k + mid] = (x + mod - y) % mod;
			}
		}
	} 
	if (type == 1) return ;
	int Inv = quick_pow (limit,mod - 2);
	for (Int i = 0;i < limit;++ i) a[i] = 1ll * a[i] * Inv % mod;
}

int c[MAXN];

void Solve (int len,int *a,int *b){
	if (len == 1) return b[0] = quick_pow (a[0],mod - 2),void ();
	Solve ((len + 1) >> 1,a,b);
	limit = 1,l = 0;
	while (limit < (len << 1)) limit <<= 1,l ++;
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	for (Int i = 0;i < len;++ i) c[i] = a[i];
	for (Int i = len;i < limit;++ i) c[i] = 0;
	NTT (c,1);NTT (b,1);
	for (Int i = 0;i < limit;++ i) b[i] = 1ll * b[i] * (2 + mod - 1ll * c[i] * b[i] % mod) % mod;
	NTT (b,-1);
	for (Int i = len;i < limit;++ i) b[i] = 0;
}

int C[MAXN],D[MAXN];

void Sqrt (int *a,int *b,int n){
	if (n == 1) return b[0] = a[0],void ();
	Sqrt (a,b,n >> 1);
	for (Int i = 0;i < n;++ i) C[i] = a[i];
	Solve (n,b,D);
	NTT (C,1);NTT (D,1);
	for (Int i = 0;i < limit;++ i) D[i] = 1ll * D[i] * C[i] % mod;
	NTT (D,-1);
	for (Int i = 0;i < limit;++ i) b[i] = 1ll * (b[i] + D[i]) % mod * inv2 % mod,C[i] = D[i] = 0; 
}

int read (){
	int x = 0;char c = getchar();int f = 1;
	while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}
	while (c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + c - '0';c = getchar();}
	return x * f;
}

void write (int x){
	if (x < 0){x = -x;putchar ('-');}
	if (x > 9) write (x / 10);
	putchar (x % 10 + '0');
}

int n,m,G[MAXN],F[MAXN],T[MAXN];

signed main(){
	n = read (),m = read ();
	for (Int i = 1,w;i <= n;++ i){
		w = read ();
		if (w <= m) F[w] ++;
	}
	while (limit <= m) limit <<= 1,l ++;
	for (Int i = 0;i < limit;++ i) F[i] = (i == 0) ? 1 + mod - 4 * F[i] : mod - 4 * F[i];
	Sqrt (F,T,limit),T[0] ++,Solve (limit,T,G);
	for (Int i = 1;i <= m;++i) write (2 * G[i] % mod),putchar ('
');
	return 0;
}