【CF438E】 The Child and Binary Tree 简易题解

题目大意

$\ \ \ \ \ \ \,$      给你 $n$n 和 $m$m，和大小为 $n$n 的集合 $C$C。

$\ \ \ \ \ \ \,$      需要你统计点权在集合 $C$C 内，且点权之和分别为 $[1,m]$[1,m] 的二叉树个数。

想法

$\ \ \ \ \ \ \,$      根据题目，我们可以想到$DP$DP公式求解：

$f(n)= \begin{cases} 1, & \text {$(n=0)$} \\ \sum_{i=1}^{n}g(i)\sum_{j=0}^{n-i}f(j)\cdot f(n-i-j), & \text{$(n > 0)$} \end{cases}$f(n)={1,∑i=1n​g(i)∑j=0n−i​f(j)⋅f(n−i−j),​(n=0)(n>0)​

$\ \ \ \ \ \ \,$      其中：

• $f(i)$f(i)意思是且点权之和 $i$i 的二叉树个数。
• $g(i)$g(i)意思是集合 $C$C 中是否含有元素 $i$i，既 $g(i)=[i\in C]$g(i)=[i∈C] 。

$\ \ \ \ \ \ \,$      怎么得到这个公式的就不说了，还是比较显然的 （雾 。但是很明显复杂度过不去。我们把它们写成生成函数会好一些 （计数题套路？）：

$\ \ \ \ \ \ \,$      令函数 $F$F 为序列 $f(x)$f(x) 的生成函数，函数 $G$G 为序列 $g(x)$g(x)的生成函数。

$\ \ \ \ \ \ \,$      可以得到：

$F=G*F^2+1$F=G∗F2+1

$\ \ \ \ \ \ \,$      解得：

$F=\frac{2}{1\pm\sqrt{1-4G}}$F=1±1−4G​2​

$\ \ \ \ \ \ \,$      那么是加号还是减号啊？已知$F_0=1$F0​=1。而题目保证 $(1\leq c_i \leq 10^5)$(1≤ci​≤105)，所以有$G_0=0$G0​=0。那么带入可以得到应该是取加号。

$\ \ \ \ \ \ \,$      所以说只需要求出多项式$\frac{2}{1+\sqrt{1-4G}}$1+1−4G​2​的$[1,m]$[1,m]项就好了。

$\ \ \ \ \ \ \,$      格式挺清新的，需要求逆和开根，模板直接往上套就好了呢：【多项式的操作大赏】。我写的开根比较麻烦，还要写 $\ln$ln 和 $\exp$exp，然后 $\ln$ln 还要写求积分和求导。所以说……基本上……所有模板都用到了。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
	int x=0,f=1;char ch;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
	if(f)return x;else return -x;
}
const int mod=998244353,mod_g=3,N=1600000;
int R[N];
int power(int a,int b){
  	int ans=1;
  	for(;b;b>>=1,a=1ll*a*a%mod)
	if(b&1)ans=1ll*ans*a%mod;
  	return ans;
}
#define Inv(x) power(x,mod-2)
int Polynomial_init(int n){
	int len;for(len=1;len<=n;len<<=1);
	return len;
}
void NTT(int *a,int f,int la){
	int n=la;
  	for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
  	for(int i=1;i<n;i<<=1){
    	int gn=power(mod_g,(mod-1)/(i<<1));
    	for(int j=0;j<n;j+=(i<<1)){
      		int g=1;
      		for(int k=0;k<i;k++,g=1ll*g*gn%mod){
	        	int x=a[j+k],y=1ll*g*a[i+j+k]%mod;
	        	a[j+k]=(x+y)%mod;a[i+j+k]=(x-y+mod)%mod;
	      	}
    	} 
  	}
  	if(f==-1){
   		reverse(a+1,a+n);
    	int inv=Inv(n);
    	for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
  	}
}
int Convolution(int *a,int *b,int la,int lb){
	int n=la,m=lb;
	int L=0;for(m+=n,n=1;n<m;n<<=1)L++;
	for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	NTT(a,1,n);NTT(b,1,n);
	for(int i=0;i<=n;i++)a[i]=1ll*a[i]*b[i]%mod;
	NTT(a,-1,n);
	return m;
}
int C[N];
void Inverse(int *a,int *b,int len){
  	if(len==1){b[0]=Inv(a[0]);return;}
  	Inverse(a,b,(len+1)>>1);
  	int L=0,n=1;
  	for(;n<(len<<1);n<<=1)L++;
  	for(int i=1;i<n;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<n;i++)C[i]=0;
  	NTT(C,1,n);NTT(b,1,n);
  	for(int i=0;i<=n;i++)b[i]=1ll*(2ll-1ll*C[i]*b[i]%mod+mod)%mod*b[i]%mod;
  	NTT(b,-1,n);
  	for(int i=len;i<n;i++)b[i]=0;
}
void Derivation(int *a,int *b,int n){
	for(int i=1;i<n;i++)
  	b[i-1]=1ll*i*a[i]%mod;
	b[n-1]=0;
}
void Integral(int *a,int *b,int n){
	for(int i=1;i<n;i++)
  	b[i]=1ll*Inv(i)*a[i-1]%mod;
	b[0]=0;
}
int A[N],B[N];
void Logarithmic(int *a,int *b,int len){
	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
  	Derivation(a,A,len);
  	memset(C,0,sizeof(C));
  	Inverse(a,B,len);
  	Convolution(A,B,len,len);
  	Integral(A,b,len);
}
int D[N];
void Exponential(int *a,int *b,int len){
  	if(len==1){b[0]=1;return;}
  	Exponential(a,b,len>>1),Logarithmic(b,D,len);
  	D[0]=(1ll*a[0]+1ll-D[0]+mod)%mod;
  	for(int i=1;i<len;++i) D[i]=(1ll*a[i]-D[i]+mod)%mod;
  	Convolution(b,D,len<<1,len<<1);
  	for(int i=len;i<(len<<1);++i) b[i]=D[i]=0;
}
int E[N];
void Kth_root(int *a,int *b,int len,int k){
	Logarithmic(a,E,len);
	for(int i=1;i<=len;i++)E[i]=499122177ll*E[i]%mod;
	Exponential(E,b,len);
}
int n,m,F[N],G[N];
int main()
{
	n=read();m=read();
  	for(int i=1;i<=n;++i)++G[read()];
  	int len=Polynomial_init(m);
  	for(int i=0;i<len;++i)G[i]=(mod-(4ll*G[i]%mod))%mod;
  	++G[0];
  	Kth_root(G,F,len,2);
  	for(int i=0;i<len;++i)G[i]=0;
  	F[0]=(F[0]+1)%mod;
  	Inverse(F,G,len);
  	for(int i=0;i<=m;++i)G[i]=(2ll*G[i])%mod;
  	for(int i=1;i<=m;++i)printf("%d\n",G[i]);
	return 0;
}