题目大意
平衡二叉树(AVL树），是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为AVL树。 现在问题来了，给定AVL树的节点个数n，求有多少种形态的AVL树恰好有n个节点。(n<=2000)
解答
一开始想先构个接近n的满二叉树，用组合数搞搞，然后发现naive了。后来还是老老实实的用dp来解决。
由于AVL的层数很小，是1.5*log(n)级别的，所以我们可以用dp[dep][i]表示深度为dep结点数为i的方案数。然后我们每次固定树的根，枚举左右儿子个数进行转移。
转移方程如下：
dp[dep][ i ]=∑ (dp[dep-1][ j ] × dp[dep-1][ i-j-1 ] + dp[dep-1][ j ] × dep[dep-2][ i-j-1 ] + dp[dep-2][ j ] × dep[dep-1][ i-j-1 ] )( 0<=j<i )
时间复杂度是O(n^2 × log(n))
由于AVL树的最高高度有一个至少结点数的递推公式，minf[0]=0，minf[1]=1，minf[i]=minf[i-1]+minf[i-2]+1(i>=2)。所以每个深度的结点数有上下界（上届是满二叉树的时候），用这个性质可以做一个小小的优化，避免无用的枚举。
如果这题的n扩大到10000，甚至更多，我们观察递推公式，由dep-1和dep-2推出dep，可以发现左右子树结点个数的和是i-1，满足fft的式子。因此我们可以用fft优化做到O(n × (log(n))^2)的复杂度。
倘若把这题的二叉树条件换成四叉树，其他都不变，可以变成一道很有意思的题目，dp的时候要注意技巧。这个问题和codeforces 300D基本一样，不过cf这题的题目背景和内容更加有趣。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define bll long long
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
const int maxn=2048+10;
const int modd=1000000007;
int N;
int minf[25],maxf[25];
int dp[25][maxn];
int Done()
{
minf[0]=maxf[0]=0;
minf[1]=maxf[1]=1;
For(i,2,20)
{
minf[i]=minf[i-1]+minf[i-2]+1;
maxf[i]=(1<<i)-1;
}
memset(dp,0,sizeof dp);
dp[0][0]=1;
dp[1][1]=1;
For(i,2,N)
{
For(dep,2,20)
if (minf[dep]<=i && i<=maxf[dep])
{
int ret=0;
For(j,minf[dep-1],min(maxf[dep-1],i-1))
{
int k=i-1-j;
ret=(ret+(bll)dp[dep-1][j]*dp[dep-1][k]) %modd;
ret=(ret+(bll)dp[dep-1][j]*dp[dep-2][k]) %modd;
}
For(j,minf[dep-2],min(maxf[dep-2],i-1))
{
int k=i-1-j;
ret=(ret+(bll)dp[dep-2][j]*dp[dep-1][k]) %modd;
}
dp[dep][i]=ret;
}
}
int ans=0;
For(dep,1,20)
ans=(ans+dp[dep][N]) %modd;
return ans;
}
int main(int argc, char* argv[])
{
for (; scanf("%d",&N)!=EOF; )
{
int ans=Done();
printf("%d\n",ans);
}
return 0;
}
