讲解见http://www.cnblogs.com/IMGavin/p/5621370.html， 4 可重组合
dfs枚举子树的节点个数，相乘再累加
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<algorithm>
6 using namespace std;
7 typedef long long LL;
8
9 LL f[];
LL cm(LL n, LL m){
m = min(n - m, m);
LL ans = ;
for(LL i = ; i <= m; i++){
ans = ans * (n - m + i) / i;
}
return ans;
}
void dfs(int n, int x, int r, LL mul){
if(r == ){
f[n] += mul;
}else{
for(int i = x; i < n; i++){
for(int j = ; i * j <= r; j++){
dfs(n, i + , r - i * j, mul * cm(f[i] + j - ,j ) );
}
}
}
}
int main(){
memset(f, , sizeof(f));
f[] = ;f[] = ;
for(int i = ; i <= ; i++){
dfs(i, , i - ,);
}
int n;
while(~scanf("%d", &n)){
printf("%I64d\n", f[n]);
}
return ;
46 }