hdu 5136(dp计数)

题目链接

题意:求直径为K的每一个点的边数不超过3的结构相互不同构的树有多少种?


解法:把树的直径拉开,两边就是两棵2叉树了。子问题:1个深度为m的不同构的2叉树有多少种?dp[i]表示深度为i的个数。sum[i]表示dp的前缀和。转移方程就是:dp[i+1]=dp[i]*sum[i⑴]+dp[i]+dp[i]*(dp[i]⑴)/2;

然后回到原问题:如果K是偶数(想象中间有个虚拟的不动点),则两边是两棵深度为K/2的2叉树,答案为:dp[i]*(dp[i]⑴)/2+dp[i]

如果K为奇数,则中间还有1个节点:他也是颗2叉树,则分两种大情况:

                               第3个2叉树的深度小于K/2,则sum[K/2⑴]*(dp[K/2]*(dp[K/2]⑴)/2+dp[K/2])便可;

                               第3个2叉树的深度等于K/2,则分3类讨论:1 3棵2叉树结构1样dp[K/2] 2 两棵1样,2 另外一棵不1样:dp[K/2]*(dp[K/2]⑴) 3 3棵都不1样:dp[K/2]*(dp[K/2]⑴)*(dp[K/2]⑵)/6


代码:

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e⑻
#define zero(_) (abs(_)<=eps)
const double pi=acos(⑴.0);
typedef long long LL;
const int Max=100010;
const LL INF=1000000007;
LL ans[Max];
LL sum[Max];
LL powa(LL t,LL p)
{
LL ans=1;
while(p)
{
if(p&1)
ans=(ans*t)%INF;
t=(t*t)%INF;
p>>=1;
}
return ans;
}
LL getreverse(LL t)
{
return powa(t,INF⑵)%INF;
}
LL getans(int t)
{
int l=t/2;
LL rem=((ans[l]*((ans[l]⑴+INF)%INF)%INF*getreverse((LL)2))%INF+ans[l])%INF;
//cout<<ans[l]<<" "<<rem<<endl;
if(t&1)
{
rem=(rem*sum[l⑴])%INF;
rem=(rem+ans[l])%INF;
rem=(rem+ans[l]*(ans[l]⑴)%INF)%INF;
rem=(rem+ans[l]*((ans[l]⑴+INF)%INF)%INF*((ans[l]⑵+INF)%INF)%INF*getreverse(6)%INF)%INF;
return rem;
}
else
{
return rem;
}
}
LL geter(int t)
{
return (ans[t⑴]*sum[t⑵]%INF+ans[t⑴]*((ans[t⑴]⑴+INF)%INF)%INF*getreverse(2)%INF+ans[t⑴])%INF;
}
void init()
{
ans[0]=1;
ans[1]=1;
ans[2]=2;
sum[0]=1;
sum[1]=2;
sum[2]=4;

for(int i=3; i<Max; i++)
{
ans[i]=geter(i);
sum[i]=(sum[i⑴]+ans[i])%INF;
}

}
int main()
{
init();
int n;
while(cin>>n&&n)
{
cout<<getans(n)<<endl;
}
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » hdu 5136(dp计数)
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡