题目描述
农夫约翰正在考虑买进一批新的牛群。
在这个新的牛群中,每头母牛都会生两个孩子。
牛的关系可以用一个包含 N 个节点的二叉树来表示,此二叉树应满足下列性质:
每个节点的子节点数为 0 或 2。
- 树的高度等于 K。树的高度是指从根节点到任一叶子节点的最长路径上的节点数。叶子节点是指没有子节点的节点。
- 请问,共有多少种可能的谱系结构?
换句话说,共有多少种满足上述性质的 N 个节点的二叉树?
请输出对 9901 取模后的答案。
输入格式
共一行,包含两个整数 N 和 K。
输出格式
共一行,包含一个整数,表示对 9901 取模后的答案。
数据范围
$3≤N<200$
$1<K<100$
输入样例
5 3
输出样例
2
算法:DP
时间复杂度:$O(N^2K)$
$f(i, j)$ 的含义为:节点数为 $i$, 高度最大为 $j$,其值为总方案数。
先上图
由此,状态转移方程为:$f(n, k) = \sum_{i=1}^n f(i, k - 1) \times f(n - i - 1, k - 1)$
C++ 代码
#include <iostream>
using namespace std;
const int N = 210, M = 110, MOD = 9901;
int n, m;
int f[N][M];
int main()
{
cin >> n >> m;
// 初始化根节点
for (int i = 1; i <= m; ++i) {
f[1][i] = 1;
}
// 节点个数应该从 2 开始枚举
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= i - 2; ++k) { // 用于枚举每个状态
f[i][j] += f[k][j - 1] * f[i - k - 1][j - 1];
f[i][j] %= MOD;
}
}
}
cout << (f[n][m] - f[n][m - 1] + MOD) % MOD << endl;
return 0;
}