题目链接
题意：求直径为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;
}
波比源码 » hdu 5136(dp计数)
