1. 知识点

#取模 #dp? #n节点的二叉树种类

2. 题目

略

3. 思路

题目要求所有节点的孩子数量为0或者为2 ，那么即每个节点都有一个同伴（根节点除外），即他的父节点还有另一个子节点。

所以加上根节点，一个根节点+偶数=奇数。所以n为偶数的好二叉树为0个。

如果为奇数：

• 除去根节点，则n-1为偶数。必须两两配对，那么一共有(n-1)/2对。即求（n-1）/2个节点能组成多少种二叉树的情况。

n节点的二叉树数量

0个节点二叉树数量为f(0)=1

1个节点二叉树数量为f(1)=1

2个节点二叉树数量为根和左孩子 或者 根和右孩子。f(2)=1+1 =2

3个节点二叉树数量为根加左两个孩子 或者 根加右两个孩子 或者 根加左加右。f(3) = f(2)f(0) + f(0)f(2)+f(1)f(1) =2 + 2 + 1 =5

4个节点二叉树数量同理，f(4)=f(3)(0)+f(2)(1)+f(1)(2)+f(0)(3) = 5+2+2 +5 =14

so：f(n) = f(n-1)f(0) + f(n-2)f(1) + ... + f(0)f(n-1)

so:

回到题目

将本题的(n-1)/2为节点的数量带入上式中的n即可。即dp，时间复杂度.

4. 题解

n = int(input())

if n%2 ==0:
    print(0)
    exit()

dp = [0 for i in range(n//2+1)]
dp[0]=1
dp[1]=1
#O(n2)
for i in range(2,n//2+1):
    for j in range(i):
        dp[i] += dp[j]*dp[i-1-j]


print(dp[-1]%1000000007)