讲解见， 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[

41];

10 LL cm(LL n, LL m){

11     m = min(n - m, m);

12     LL ans = 

1;

13     

for(LL i = 

1; i <= m; i++){

14         ans = ans * (n - m + i) / i;

15     }

16     

return ans;

17 }

18 

19 

20 

void dfs(

int n, 

int x, 

int r, LL mul){

21     

if(r == 

0){

22         f[n] += mul;

23 

24     }

else{

25         

for(

int i = x; i < n; i++){

26             

for(

int j = 

1; i * j <= r; j++){

27                 dfs(n, i + 

1 , r - i * j, mul * cm(f[i] + j - 

1,j ) );

28             }

29         }

30 

31     }

32 }

33 

int main(){

34     memset(f, 

0  , 

sizeof(f));

35     f[

1] = 

1;f[

2] = 

1;

36     

for(

int i = 

3; i <= 

40; i++){

37         dfs(i, 

1, i - 

1 ,

1);

38     }

39 

40     

int n;

41     

while(~scanf(

"

%d

", &n)){

42         printf(

"

%I64d\n

", f[n]);

43 

44     }

45     

return 

0;

46

 }