#C231113B. 计树(tree)

标签（Label）

动态规划
滚动数组

网址（Website）

$\qquad$ 题目详情 - 计树(tree) - Super

$\qquad$ 题解 - 计树(tree) - Super

题目（Problem）

统计满足以下条件的 $n$ 个结点的二叉树个数：

第 $i$ 个结点的儿子个数在 $\left[l_{i}, r_{i}\right]$ 之间。
如果第 $i$ 个结点不为叶子，且其儿子的最大编号为 $k_{i}$, 则需要满足 $k_{i}>i$ 。

注意左右儿子是区分的。

我们认为两棵树不同，当且仅当在某个点在两棵树中的父亲不同，或是左右儿子不同。

答案对 $10^{9}+7$ 取模。

范围：对于所有数据, 有 $1 \leq T \leq 3$；$1 \leq n \leq 300$；$0 \leq l_{i} \leq r_{i} \leq 2$ 。

题解（Solution）

算法分析

设 $ f_{i,j,k} $ 表示考虑了前 $ i $ 个结点，有 $ j $ 个结点没有父亲（即当前图形态为 $ j $ 棵树的森林），且前 $ i $ 个点还缺少 $ k $ 个儿子的状态。在转移的过程中，我们钦定第 $ i+1 $ 个点的儿子数量 $ l $ ，令 $fa$ 表示父结点编号，$cur$ 表示当前结点编号，$son$ 与 $sonl,sonr$ 分别表示 $l==1$ 和 $l==2$ 时的儿子的编号：

当 $ l = 0 $ 时：

新开一棵树：$ f_{i,j,k} \rightarrow f_{i+1,j+1,k}$ ，此时$fa<cur$。
接在之前某个缺儿子的结点下面：$k\times f_{i,j,k} \rightarrow f_{i+1,j,k-1} $ ，此时 $fa>cur$ 。

当 $ l = 1 $ 时：

转移方式与 $ l = 0 $ 相同，但注意转移系数为 2，因为需要钦定这个点的儿子是左儿子还是右儿子。
新开一棵树：$fa<cur$ 且 $son>cur$ 。
接在之前某个缺儿子的结点下面：$fa>cur$ 且 $son>cur$ 。

当 $ l = 2 $ 时：

与 $ l = 0/1 $ 有相同的转移方式。额外的：
将之前某个没有父亲的结点接在它下面：$ 2 \times j \times f_{i,j,k} \rightarrow f_{i+1,j,k+1} $，

乘二是因为要钦定它接在左儿子还是右儿子。

此时 $fa>cur$ 、 $sonl<cur$ 、$sonr>cur$ 。

将之前某个没有父亲的结点接在它下面，并将它接在之前某个缺儿子的结点下面：$ 2 \times (j-1) \times k \times f_{i,j,k} \rightarrow f_{i+1,j-1,k} $

$ j-1 $ 是因为，你接在一个缺儿子的结点下面，而这个结点所在的树的根就不能接在你下面了。

此时 $fa<cur$ 、 $sonl<cur$ 、$sonr>cur$ 。

总时间复杂度为 $ O(Tn^3) $ 。

概念解释：

由于题目中对儿子的编号要求：

当新开一棵树时，其所有的儿子（可能没有）的编号都会比当前结点大，且当前结点未来的父亲编号一定比这个点大（按照题目要求，这个时候这个点只能接上 $l==2$ 的父亲）；
当这个点接在某个缺少儿子的结点下面时，只会接在 $l==1$ 或者已经接了一个点的 $l==2$ 的结点上（$l==2$的已经接了的儿子编号应小于那个 $l= =2$ 的结点），此时当前点的编号一定大于接上的那些结点；
当这个点下面接上一个没有父亲的结点时，正如“1.”中的括号所说，这个点的编号大于它儿子的编号，那么下一次就只能接编号比它更大的儿子，正如“2.”中所说；
当这个点下面接上一个没有父亲的结点，同时自己上面有接上一个结点时，父亲的编号和儿子的编号都小于自己。

综上，对于一个结点，如何考虑不同的情况呢？只需要区分它的父亲的编号和自己的关系、它的儿子的编号和自己的关系便可以考虑所有情况。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int mod = 1e9+7;
const int N = 305;
inline void add(int &x,int y){if((x+=y)>mod) x-=mod;}
int tid,T,n,l[N],r[N],f[2][N][N];
// f[i][j][k]: 前 i 个结点  目前有 j 棵树  还有 k 个结点没有儿子
inline void solve(){
	cin>>n;For(i,1,n) cin>>l[i]>>r[i];
	memset(f[0],0,sizeof f[0]);f[0][0][0]=1;
	For(i,1,n){
		memset(f[i&1],0,sizeof f[i&1]);
		For(j,0,i-1){
			For(k,0,n){
				if(!f[i-1&1][j][k]) continue;//如果上一个结点在当前状态下没有可能，跳过
				if(l[i]==0){
					add(f[i&1][j+1][k],f[i-1&1][j][k]);//新开一棵树
					if(k) add(f[i&1][j][k-1],k*f[i-1&1][j][k]%mod);//接在之前的点上 
				}if(l[i]<=1 && r[i]>=1){
					add(f[i&1][j+1][k+1],2*f[i-1&1][j][k]%mod);//新开一棵树，可能是左儿子，也有可能是右儿子 
					add(f[i&1][j][k],2ll*k*f[i-1&1][j][k]%mod);//缺儿子的结点数量不会变 
				}if(r[i]==2){
					add(f[i&1][j+1][k+2],f[i-1&1][j][k]);//新开一棵树
					add(f[i&1][j][k+1],1*f[i-1&1][j][k]*k%mod);//接在之前的点上
					add(f[i&1][j][k+1],2*f[i-1&1][j][k]*j%mod);//让左儿子或右儿子接上一棵树
					//如果至少有一棵子树：将一棵子树接在自己身上（接左或接右），自己接在一棵子树上 
					if(j>1) add(f[i&1][j-1][k],2*f[i-1&1][j][k]*k%mod*(j-1)%mod);
				}
			} 
		}
	}cout<<f[n&1][1][0]<<'\n';
} 

signed main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>tid>>T;
	while(T--) solve();
	return 0;
}