HDU 5136 Yue Fei's Battle

題意：求直徑上有K個點的不同構樹個數（每個點度不超過3）。

二叉樹滿足每個點度不超過3，把直徑從中間切開，兩邊就是二叉樹了。

設dp[i] = 深度為i的不同構二叉樹個數。

   sum[i] = 深度不超過i的不同構二叉樹個數。

那麼二叉樹的兩個分支有3種情況：

一個分支深度為i-1, 另一個分支深度小于i-1，有dp[i-1] * sum[i-2]種方法；

兩個分支深度都是i-1：

兩個分支不一樣，有dp[i-1]*(dp[i-1]-1)/2種方法；

兩個分支一樣，有dp[i-1]種方法。

dp[i] = dp[i-1]*sum[i-2] + dp[i-1]*(dp[i-1]+1)/2

 i = K / 2

當K為偶數時，兩邊的二叉樹深度都是K/2，

考慮兩邊可能相同，可能不同，方案數為dp[i]*(dp[i]+1)/2;

當K為奇數時，中間的點連接配接3個分支，至少有2個分支深度為K/2。

當3個分支有一個分支深度小于K/2，方案數 dp[i]*(dp[i]+1)/2*sum[i-1]

當3個分支深度都是K/2：

當3個分支都相同，方案數 dp[i]

當3個分支2個相同，方案數為 dp[i] * (dp[i] - 1)

當3個分支互不相同，方案數 C(dp[i], 3)

所有情況加起來就行了。

Yue Fei's Battle

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others)

Total Submission(s): 194    Accepted Submission(s): 59

Problem Description Yue Fei is one of the most famous military general in Chinese history.He led Southern Song army in the wars against the Jin dynasty of northern China. Yue Fei achieved a lot of victory and hopefully could retake Kaifeng ,the former capital of Song occupied by Jin. Fearing that retaking Kaifeng might cause the Jin to release former Emperor Song Qinzong, threatening his throne, Emperor Song Gaozong took some corrupted officers' advice, sending 12 urgent orders in the form of 12 gold plaques to Yue Fei, recalling him back to the capital.

Then Yue Fei was put into prison and was killed under a charge of "maybe there is" treason. But later Yue Fei was posthumously pardoned and rehabilitated, and became a symbol of loyalty to the country. The four corrupted officers who set him up were Qin Hui,Qin Hui's wife Lady Wang, Moqi Xie and Zhang Jun. People made kneeling iron statues of them and put the statues before Yue Fei's tomb (located by the West Lake, Hangzhou). For centuries, these statues have been cursed, spat and urinated upon by people. (Now please don't do that if you go to Hangzhou and see the statues.)

One of the most important battle Yue Fei won is the battle in Zhuxian town. In Zhuxian town, Yue Fei wanted to deploy some barracks, and connected those barracks with roads. Yue Fei needed all the barracks to be connected, and in order to save money, he wanted to build as less roads as possible. There couldn't be a barrack which is too important, or else it would be attacked by enemies. So Yue Fei required that NO barrack could connect with more than 3 roads. According to his battle theory, Yue Fei also required that the length of the longest route among the barracks is exactly K. Note that the length of a route is defined as the number of barracks lied on it and there may be several longest routes with the same length K.

Yue Fei wanted to know, in how many different ways could he deploy the barracks and roads. All barracks could be considered as no different. Yue Fei could deploy as many barracks as he wanted.

For example, if K is 3,Yue Fei had 2 ways to deploy the barracks and roads as shown in figure1. If K is 4, the 3 kinds of layouts is shown in figure 2. (Thick dots stand for barracks, and segments stand for roads):

Please bring your computer and go back to Yue Fei's time to help him so that you may change the history.  

Input The input consists of no more than 25 test cases.

For each test, there is only one line containing a integer K(1<=K<=100,000) denoting the length of the longest route.

The input ends by K = 0.  

Output For each test case, print an integer denoting the number of different ways modulo 1000000007.  

Sample Input

3
4
0
        

Sample Output

2
3
        

Source 2014ACM/ICPC亞洲區廣州站-重制賽（感謝華工和北大）  

#include <bits/stdc++.h>
using namespace std;
#define prt(k) cerr<<#k" = "<<k<<endl

typedef long long ll;
const ll mod = 1e9 + 7;
ll pmod(ll a, ll n)
{
    ll ret = 1;
    for (; n; n>>=1, a=a*a%mod)
        if (n&1)
        ret = ret * a % mod;
    return ret;
}
ll getinv(ll a)
{
    return pmod(a, mod - 2);
}
const int N = 100100;
ll dp[N + 5], sum[N + 5];
const ll inv2 = getinv(2);
ll sub(ll a, ll b)
{
    return (a - b + mod) % mod;
}
void init()
{
    dp[0] = 1;
    dp[1] = 1;
    sum[0] = 1;
    sum[1] = 2;
    for (int i=1;i<N;i++)
    {
        dp[i+1] = (dp[i] * sum[i-1] % mod);
        dp[i+1] = (dp[i+1] + (dp[i] + 1)%mod * dp[i] % mod * inv2 % mod) % mod;
        sum[i+1] = (sum[i] + dp[i+1]) % mod;
    }
}
ll C3(ll a)
{
    return ((a*sub(a,1)%mod) * sub(a,2) % mod) * getinv(6) % mod;
}
ll f(int K)
{
    int i = K / 2;
    ll ans = ((dp[i] * (dp[i] +  1)%mod) % mod * inv2 % mod ) % mod;
    ll tmp = ans;
    if (K%2==0) {
        return ans;
    }
    ans = (ans * sum[i-1]) % mod;
    ans = (ans + dp[i]) % mod;
    ans = (ans + (dp[i]-1+mod)%mod * dp[i] % mod) % mod;
    ans = (ans + C3(dp[i])) % mod;
    return ans;
}
int main()
{
    int K;
    init();
    while (cin>>K, K)
    {
        ll ans = f(K);
        cout<<ans<<endl;
    }
    return 0;
}