传送门

一个深度为i的树可以由一个根节点外加两个深度为i-1的树组成,这就决定了DP该怎么写。

然而我真的没有想到。

f[i][j]表示深度为i节点数为j的个数

sum[i][j]表示深度小于等于i节点树为j的个数

#include <cstdio>
#define N 402
#define p 9901 int n, m;
int f[N][N], sum[N][N];
//f[i][j]表示深度为i节点数为j的个数
//sum[i][j]表示深度<=i节点数为j的树的个数 int main()
{
int i, j, k;
scanf("%d %d", &n, &m);
if(!(n & 1))
{
puts("0");
return 0;
}
f[1][1] = sum[1][1] = 1;
for(i = 2; i <= m; i++)
{
//两个深度都是i-1
for(j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
f[i][1 + j + k] = (f[i][1 + j + k] + f[i - 1][j] * f[i - 1][k] % p) % p;
//一个深度为i-1
for(j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
f[i][1 + j + k] = (f[i][1 + j + k] + f[i - 1][j] * sum[i - 2][k] * 2 % p) % p;
//更新sum
for(j = 1; j <= n; j++)
sum[i][j] = (sum[i - 1][j] + f[i][j]) % p;
}
printf("%d\n", f[m][n]);
return 0;
}

  

最新文章

  1. ASP.NET Identity 2新增双重认证、帐号锁定、防伪印章功能并修复了一些bug
  2. PHP获取Cookie模拟登录CURL
  3. 鼠标点击input时,placeholder中的提示信息消失
  4. ServiceStack 入门(二)
  5. SQL SERVER SQLOS的任务调度
  6. socket.io搭配pm2(cluster)集群解决方案
  7. x86-64栈帧中的“红色区域” red zone of stack frame on x86-64
  8. javascript 思维导图 总结
  9. ORACLESQL语句的优化
  10. Centos7 Lnmp的环境搭建
  11. c语言实现:三子棋
  12. java相关知识点
  13. vscode運行vue和html
  14. lvm管理卷之缩减卷大小
  15. 基本数据类型、包装类、String之间的转换
  16. Pwnium CTF2014 – MatterOfCombination writeup
  17. CF-877E-线段树+哈希
  18. 2.22 JS处理富文本
  19. 用singleton单例模式实现一个模块
  20. preg_replace正则表达式的使用

热门文章

  1. C. Two strings 二分 + 预处理
  2. laravel5.5文件上传
  3. 百度地图对https的支持
  4. redis 可视化管理工具
  5. MySQL(MMM架构使用)
  6. 数据库和java的类型转化
  7. bat运行当前路径下程序
  8. iis如何在dos中注册
  9. phphstrom改变项目中文件排列方式
  10. 笔试算法题(06):最大连续子数组和 &amp; 二叉树路径和值