首页 > 代码库 > [luoguP1472] 奶牛家谱 Cow Pedigrees（DP）
[luoguP1472] 奶牛家谱 Cow Pedigrees（DP）
传送门
一个深度为i的树可以由一个根节点外加两个深度为i-1的树组成，这就决定了DP该怎么写。
然而我真的没有想到。
f[i][j]表示深度为i节点数为j的个数
sum[i][j]表示深度小于等于i节点树为j的个数
#include <cstdio>#define N 402#define p 9901int 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;}
[luoguP1472] 奶牛家谱 Cow Pedigrees（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。