Yue Fei's Battle(组合计数递推)

//求一个直径为 k 的树有多少种形态，每个点的度不超过 3

// 非常完美的分析，学到了，就是要细细推，并且写的时候要细心

还有除法取模需要用逆元

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

using namespace std;

#define MOD 1000000007

#define LL long long

#define MX 100005

LL dp[MX];

LL sum[MX];

LL inv2;

LL inv6;

LL quick(LL a,LL b)

{

    LL ret = ;

    while (b)

    {

        if (b&) ret = ret*a%MOD;

        a = a*a%MOD;

        b/=;

    }

    return ret;

}

void Init()

{

    inv2 = quick(,MOD-);

    inv6 = quick(,MOD-);

    dp[]=,sum[]=;

    dp[]=,sum[]=;

    for (int i=;i<MX;i++)

    {

        dp[i] = dp[i-]*(dp[i-]-)%MOD*inv2%MOD;

        dp[i] = (dp[i] + dp[i-])%MOD;

        dp[i] = (dp[i] + dp[i-]*sum[i-]%MOD)%MOD;

        sum[i]=(sum[i-]+dp[i])%MOD;

    }

}

int main()

{

    int n;

    Init();

    while (scanf("%d",&n)&&n)

    {

        if (n%==)

        {

            int i = n/;

            int ans = (dp[i]+dp[i]*(dp[i]-)/)%MOD;

            printf("%d\n",ans);

        }

        else

        {

            int i = n/;

            int ans = (((dp[i]*(dp[i]+))%MOD*inv2%MOD)*sum[i-])%MOD;

            ans = (ans + dp[i])%MOD;

            ans = (ans + (dp[i]*(dp[i]-)%MOD)%MOD)%MOD;

            ans = (ans + dp[i]*(dp[i]-)%MOD*(dp[i]-)%MOD*inv6%MOD )%MOD;

            printf("%d\n",ans);

        }

    }

    return ;

}