https://blog.csdn.net/qq_45228537/article/details/103671868
题目链接：
1007 Red-black Tree (35分)
思路：
我们定义r[i][j] b[i][j]分别为以红色、黑色的点为根节点，black height为i，internel node数量为j的情况下，所能形成的树的种数。
易知b[1][1] = 1; r[0][1] = 1; b[1][2] = 2;，这是根节点具有null孩子结点的三种情况；
下面我们可以根据红黑树的性质得到具有非null孩子结点的根结点具有的递推公式：
红色结点必定有两个黑色结点的孩子：r[i][j + 1] += b[i][k] * b[i][j - k];
而黑色结点可以有任意颜色结点的孩子：b[i + 1][j + 1] += (r[i][k] + b[i][k]) * (r[i][j - k] + b[i][j - k])
由于是非null结点，这里的j + 1至少是3
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const ll mod = 1000000007;
int n;
ll r[maxn][maxn], b[maxn][maxn];
int main() {
#ifdef MyTest
freopen("Sakura.txt", "r", stdin);
#endif
scanf("%d", &n);
b[1][1] = r[0][1] = 1;
b[1][2] = 2;
for(int i = 0; i <= 10; i++){
for(int j = 2; j < n; j++){
for(int k = 1; k < j; k++){
r[i][j + 1] += b[i][k] * b[i][j - k];
r[i][j + 1] %= mod;
b[i + 1][j + 1] += (r[i][k] + b[i][k]) * (r[i][j - k] + b[i][j - k]) % mod;
b[i + 1][j + 1] %= mod;
}
}
}
ll ans = 0;
for(int i = 0; i <= n; i++) ans = (ans + b[i][n]) % mod;
printf("%lld", ans);
return 0;
}