首页 > 代码库 > hdu5136:组合计数、dp
hdu5136:组合计数、dp
题目大意:
求直径长度为N的无根二叉树的个数(同构的只算一种)
分析:
分析发现直径长度不好处理!因此考虑把问题转化一下:
假设要求直径为N的二叉树
(1)
若N为偶数,将树从直径中点的边断开,则分成了两个深度为 n/2 的有根树
(为什么要这么分?因为若深度大于 n/2 那么子书的直径就有可能大于n了!)
用num[n/2]代表n/2的有根树的个数 那么答案则为 c(num[n/2],2)+num[n/2]。。
(注意判重,c(x,x)部分代表两个子树不一样的情况,后面单独的num[]代表两个子树相同的情况,后面的统计跟这个类似,不过会麻烦一下,具体就不写了)
(2)
若N为奇数,直径中点是一个点,显然这个点可以连两个或者三个子树
其中至少有两个子树的深度为 n/2,还有一个子树可能为 0~n/2 (此处均为整数除法)
统计的时候分几种情况统计一下,!!记得注意判重,同时用 sum[n/2-1]保存 0~n/2-1的前缀和。
******
以上解决了统计答案的问题,剩下的问题是如何求出 深度为K的有根数的个数!
对于一个深度为K的树,先确定它的根,那么根的左右子树中至少有一个子树的深度为 K-1 ,另外一个可能为 0~K-1
还是记录前缀和,统计一下加上判重就好了
代码:
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define mod 1000000007#define inv2 500000004#define inv3 333333336long long sum[100010];long long num[100010];void ini(){ num[1]=sum[1]=1; num[2]=2; sum[2]=3; for(int i=3;i<=100000;i++) { num[i]=((num[i-1]+1)*num[i-1]%mod*inv2%mod+num[i-1]*(sum[i-2]+1)%mod)%mod; sum[i]=(sum[i-1]+num[i])%mod; }}int main(){ ini(); int n; while(scanf("%d",&n),n) { if(n==1) { puts("1"); continue; } long long ans; if(n%2) { ans=(num[n/2]-1)*(num[n/2])%mod*(num[n/2]-2)%mod*inv2%mod*inv3%mod; ans=(ans+num[n/2]*(num[n/2]-1)%mod)%mod; ans=(ans+num[n/2])%mod; ans=(ans+((num[n/2]-1)*num[n/2]%mod*inv2%mod+num[n/2])%mod*(sum[n/2-1]+1)%mod)%mod; } else { ans=((num[n/2]-1)*(num[n/2])%mod*inv2%mod+num[n/2])%mod; } cout<<ans<<endl; } return 0;}
hdu5136:组合计数、dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。