【CF724F】Uniformly Branched Trees 动态规划
规划 动态 Trees
2023-09-11 14:15:24 时间
【CF724F】Uniformly Branched Trees
题意:询问n个点的每个非叶子点度数恰好等于d的不同构的无根树的数目。
$n\le 1000,d\le 10$。
题解:先考虑有根树的版本。我们用$DP(n,m,k)$表示n个点,其中根的度数为m,其余点度数为d,根的最大的儿子的子树不能超过k的方案数。转移时我们可以枚举有多少个子树大小为k的。假如有i个,则贡献为:$DP(n-ik,m-i,k-1)\times{{DP(k,d-1,k-1)+i-1} \choose{i}}$,采用记忆化搜索是一个非常优秀的方法。
如果是无根树呢?如果有一个点为重心,则我们令重心为根即可。如果有两个重心,我们枚举其中一个,用组合数算一算即可。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; int n,m; ll P; ll ine[1010]; int f[1010][11][1010]; ll DP(int n,int d,int k) { k=min(k,n-1); if(f[n][d][k]!=-1) return f[n][d][k]; if((n==1&&d==m-1)||(n==1&&!d)) return 1; if(n==1||!k) return 0; int j; ll ret=DP(n,d,k-1),t=DP(k,m-1,k),tmp=1; for(j=1;j*k<n&&j<=d;j++) { tmp=tmp*(t+j-1)%P*ine[j]%P; ret=(ret+tmp*DP(n-k*j,d-j,k-1))%P; } return f[n][d][k]=ret; } int main() { scanf("%d%d%lld",&n,&m,&P); if(n==1||n==2) { puts("1"); return 0; } if((n-2)%(m-1)!=0) { puts("0"); return 0; } int i; ine[0]=ine[1]=1; for(i=2;i<=n;i++) ine[i]=P-(P/i)*ine[P%i]%P; memset(f,-1,sizeof(f)); ll ans=DP(n,m,(n-1)/2); if(!(n&1)) { ll t=DP(n/2,m-1,n/2-1); ans=(ans+t*(t+1)/2)%P; } printf("%lld",ans); return 0; }
相关文章
- 【BZOJ1831】[AHOI2008]逆序对(动态规划)
- 【CF908G】New Year and Original Order(动态规划)
- 【BZOJ1044】[HAOI2008]木棍分割(动态规划,贪心)
- 【BZOJ5252】林克卡特树(动态规划,凸优化)
- 【BZOJ3672】【NOI2014】购票(线段树,斜率优化,动态规划)
- 【BZOJ1801】【AHOI2009】中国象棋(动态规划)
- 【算法】【递归与动态规划模块】数组的最长子序列
- 动态规划(DP)之多边形游戏问题
- 大数据服务规划
- 强化学习学习笔记(二)-基于模型的动态规划方法
- Python—数据结构与算法---动态规划—DP算法(Dynamic Programing)
- LeetCode042之接雨水(相关话题:动态规划,单调栈)
- LeetCode072之编辑距离(相关话题:动态规划)
- 195、【动态规划】AcWing —— 91. 最短Hamilton路径(C++版本)
- 165、【动态规划】leetcode ——337. 打家劫舍 III:记忆化递归+动态规划(C++版本)
- 163、【动态规划】leetcode ——198. 打家劫舍(C++版本)
- 153、【动态规划】leetcode ——1049. 最后一块石头的重量 II:滚动数组(C++版本)
- 猿创征文 |【算法面试入门必刷】动态规划-线性dp(四)
- 动态规划-基础(斐波那契数、爬楼梯、使用最小花费爬楼梯、不同路径、不同路径II、整数拆分、不同的二叉搜索树)
- POJ1088 动态规划
- nyoj 49-开心的小明(动态规划, 0-1背包问题)
- nyoj 17-单调递增最长子序列 && poj 2533(动态规划,演算法)
- 动态规划