hdu 5136(dp計數)
來源：程序員人生 發布時間：2014-12-07 10:21:09 閱讀次數：2417次
題目鏈接
題意：求直徑為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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
