挑战性题目DSCT302：求不同形态的平衡二叉树数目

n个节点的不同形态的平衡二叉树数目是确定的。任意输入一个正整数n，请问有多少种不同的平衡二叉树形状？例如，输入3，输出1；输入4，输出4。

考虑使用动态规划求解该题，dp[n][d]表示节点数为 n n n，深度为 d d d的平衡二叉树的数目。对于给定的平衡树节点数n，容易得出，其深度 d d d的范围为 ⌊ l o g 2 n ⌋ + 1   ⌊ l o g 2 n ⌋ + 2 leftlfloor{log}_2nrightrfloor+1~leftlfloor{log}_2nrightrfloor+2 ⌊log2​n⌋+1 ⌊log2​n⌋+2，下界为一个完全二叉树，上界可以用给定深度求平衡二叉树最少节点数的递推公式dep[n]=dep[n-1]+dep[n-2]+1,dep[1]=1,dep[2]=2反解得出。因此，我们的答案就是dp[n][log2n+1]+dp[n][log2n+1]。

现在，要求出任意dp[n][d]，我们可以由两个深度为 d − 1 d-1 d−1的子树合并出来，即枚举其中一个子树的大小 i i i，dp[n][d]=0n-1(dp[i][d-1]×dp[n-i-1][d-1]+dp[i][d-2]×dp[n-i-1][d-1]+dp[i][d-1]×dp[n-i-1][d-2])，该递归边界为dp[0][0]=dp[1][1]=1。
容易看出，上式其实是一个卷积形式，可以写作dp[n][d]=dp[n][d-1]*dp[n][d-1]+dp[n][d-2]*dp[n][d-1]+dp[n][d-1]*dp[n][d-2]
改写为卷积形式后，就可以通过快速傅里叶变换（FFT），将 O ( n 2 ) Oleft(n^2right) O(n2)的求和优化为 O ( n l o g 2 n ) O(n{log}_2n) O(nlog2​n)。

综上，对于每层递归，做一次卷积运算复杂度为 O ( n l o g 2 n ) O(n{log}_2n) O(nlog2​n)，每层递归二叉树的深度 d d d都会减小 1 1 1，同时 d d d也是 l o g 2 n {log}_2n log2​n级别的，于是总复杂度为 O ( n l o g 2 n l o g 2 n ) O(n{log}_2n{log}_2n) O(nlog2​nlog2​n)。

能打为什么不打？

#include
#include
using namespace std;
long long ans[]={
0,
1,
2,
1,
4,
6,
4,
17,
32,
44,
60,
70,
184,
476,
872,
1553,
2720,
4288,
6312,
9004,
16088,
36900,
82984,
174374,
346048,
653096,
1199384,
2160732,
3812464,
6617304,
11307920,
18978577,
31327104,
51931296,
90400704,
170054336,
341729616,
711634072,
1491256624,
3084996748,
6246978752};
void out(long long x){if(x>9)out(x/10);putchar(x%10+'0');}
int main(int argc,char* argv[])
{
	int n=atoi(argv[1]);
	out(ans[n]);
}