A39794. 技能树
填空题
困难
知识点
题目描述
技能树
题目描述
设二叉树中每个节点的子节点数为0或2，求有N个节点高度为M的不同的二叉树有多少个
(输出 mod 9901 后的结果)。
输入
两个空格分开的整数, N和K。
输出
第 1 行: 一个整数，表示可能的技能树的个数除以9901的余数。
样例输入
5 3
样例输出
2
注释
有5个节点，高为3的两个不同的技能树
约定
n在[3,300]间,m在(1,100)间
参考答案
#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;
}
上一题
下一题