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

发表于 更新于 分类于

题目传送门：【CF438E】 The Child and Binary Tree

引入

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

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

解法

$\ \ \ \ \ \ \,$根据题目，我们可以想到$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(i)$意思是且点权之和 $i$ 的二叉树个数。
  • $g(i)$意思是集合 $C$ 中是否含有元素 $i$，既 $g(i)=[i\in C]$ 。

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

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

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

$F=G*F^2+1$

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

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

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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;
}