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