#C231113B. 计树(tree)

前言（Front talk)

动态规划的题，需要仔细地研究。

其实一般遇到动态规划的题，我都没有往动态规划这方面想，一直在思考怎么“模拟”这个过程，自然也（一定也）想不出来，之后应该多想想对于等式子的定义，再多练习推理类似的方程。

网址（Website）

题目详情 - 计树(tree) - Super

题解 - 计树(tree) - Super

题目（Problem）

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

第个节点的儿子个数在之间。
如果第个节点不为叶子，且其儿子的最大编号为, 则需要满足。

注意左右儿子是区分的。

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

答案对取模。

范围：对于所有数据, 有；；。

题解（Solution）

题解讲的很明白了。。。

代码（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;
}