简答题
偏难
#7225
技能树 设二叉树中每个节点的子节点数为0或2,求有N个节点高度为M的不同的二叉树有多少个 (输出 mod 9901 后的结果)。 时间限制:10000 内存限制…
技能树
设二叉树中每个节点的子节点数为0或2,求有N个节点高度为M的不同的二叉树有多少个
(输出 mod 9901 后的结果)。
时间限制:10000
内存限制:131072
输入
两个空格分开的整数, N和K。
输出
第 1 行: 一个整数,表示可能的技能树的个数除以9901的余数。
样例输入
5 3
样例输出
2
提示
有5个节点,高为3的两个不同的技能树。约定:n在[3,300]间,m在(1,100)间
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define N 310
#define M 110
#define mod 9901
int f[M][N], sum[N][M];
int main() {
int n, m;
scanf("%d%d", &n, &m);
f[1][1] = sum[1][1] = 1;
for (int j = 2; j <= n; j++)
f[1][j] = sum[1][j] = 0;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = 0;
for (int k = 1; k < j; k++)
f[i][j] = (f[i][j] + (2 * f[i - 1][k] * sum[i - 1][j - k - 1] -
f[i - 1][k] * f[i - 1][j - k - 1]) %
mod) %
mod;
sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
}
}
printf("%d\n", f[m][n]);
return 0;
}</pre>
这道题暂未补解析。