hdu1294 Rooted Trees Problem

http://acm.hdu.edu.cn/showproblem.php?pid=1294

　　组合数学的题，求给定结点数可以构造出多少不同的根树。

　　我的做法跟网上其他的做法有点不同，我是用整数划分的方法将一种结点数的子结点全部分解，然后用乘法原理求出组合数是多少。刚开始的时候忘记处理重复子树的会出现交换以后相同的状况，然后通过推理，发现了重复的个数跟组合数有关，所以开始的时候可以用杨辉三角构造组合数。

　　例如，如果有n个结点的子树种类有k种，同时有这样的m棵子树，那么这几棵子树的组合数就是Σ((k - i) * C(i + m - 2, m - 2))(0 <= i < k)。然后通过一个深度优先搜索每一种划分的情况，最后就可以得出组合的总数了。

　　代码如下；

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 
  5 typedef __int64 ll;
  6 
  7 ll lw, hh;
  8 const int mod = 1000000000;
  9 ll rc[41], sm;
 10 ll c[300][21];
 11 bool pr;
 12 
 13 void pre(){
 14     memset(c, 0, sizeof(c));
 15     c[0][0] = 1;
 16     for (int i = 1; i < 300; i++){
 17         c[i][0] = 1;
 18         for (int j = 1; j < 21; j++){
 19             c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
 20         }
 21     }
 22 }
 23 
 24 ll cal(ll a, int n){
 25     ll ret = 0;
 26 
 27     if (a == 1 || n == 1) return a;
 28     if (n == 2) return (a + 1) * a / 2;
 29     if (n == 3){
 30         for (ll i = 1; i <= a; i++){
 31             ret += i * (a + 1 - i);
 32         }
 33 
 34         return ret;
 35     }
 36     for (ll i = 0; i < a; i++){
 37         ret += c[i + n - 2][n - 2] * (a - i);
 38     }
 39 
 40     return ret;
 41 }
 42 
 43 int dv[41];
 44 
 45 void dfs(int rest, int last, int pos){
 46     if (!rest){
 47         ll rt = 1, ls;
 48         int cnt;
 49 
 50         ls = dv[0];
 51         dv[pos] = 0;
 52         cnt = 1;
 53         for (int i = 1; i <= pos; i++){
 54             if (dv[i] != ls){
 55                 rt *= cal(rc[ls], cnt);
 56                 cnt = 1;
 57                 ls = dv[i];
 58             }
 59             else cnt++;
 60             //if (pr) printf("%d ", dv[i - 1]);
 61         }
 62         //if (pr) printf("rt  %I64d\n", rt);
 63         sm += rt;
 64         return ;
 65     }
 66     if (last > rest) last = rest;
 67     for (int i = last; i > 0; i--){
 68         dv[pos] = i;
 69         dfs(rest - i, i, pos + 1);
 70     }
 71 }
 72 
 73 void print(){
 74     for (int i = 0; i <= 40; i++){
 75     }
 76     rc[1] = rc[2] = 1;
 77     rc[3] = 2;
 78     for (int i = 4; i <= 40; i++){
 79         if (i == 13) pr = true;
 80         else pr = false;
 81         sm = 0;
 82         dfs(i - 1, i - 1, 0);
 83         rc[i] = sm;
 84 #ifndef ONLINE_JUDGE
 85         printf(" %I64d,", sm);
 86         puts("");
 87 #endif
 88     }
 89 }
 90 
 91 int main(){
 92 #ifndef ONLINE_JUDGE
 93     freopen("in", "w", stdout);
 94 #endif
 95     pre();
 96     print();
 97 
 98 #ifdef ONLINE_JUDGE
 99     int n;
100     while (~scanf("%d", &n))
101         printf("%I64d\n", rc[n]);
102 #endif
103 
104     return 0;
105 }

yuan神的做法：http://www.cppblog.com/Yuan/archive/2010/10/22/130929.html

　　模仿yuan神打了一个代码，关键的地方在于重复集合的组合：

　　引用：由于子树不分顺序，所以枚举出来的相同规模的子树是一种有重集的组合，用公式C(n+m-1,m)

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 typedef __int64 ll;
10 ll ans[41], cnt[41];
11 
12 ll combi(ll n, ll m){
13     ll ret = 1;
14 
15     if (m > n - m) m = n - m;
16     for (ll i = 0; i < m; i++){
17         ret *= n - i;
18         ret /= i + 1;
19     }
20 
21     return ret;
22 }
23 
24 void dfs(int n, int cur, int rest){
25     if (!rest){
26         ll pro = 1;
27 
28         for (int i = 1; i <= n; i++){
29             if (cnt[i])
30                 pro *= combi(ans[i] - 1 + cnt[i], cnt[i]);
31         }
32         ans[n] += pro;
33 
34         return ;
35     }
36     if (cur > rest) return ;
37     cnt[cur]++;
38     dfs(n, cur, rest - cur);
39     cnt[cur]--;
40     dfs(n, cur + 1, rest);
41 }
42 
43 void pre(){
44     ans[1] = ans[2] = 1;
45     for (int i = 3; i <= 40; i++){
46         dfs(i, 1, i - 1);
47     }
48 }
49 
50 int main(){
51     pre();
52     int n;
53 
54     while (cin >> n){
55         cout << ans[n] << endl;
56     }
57 
58     return 0;
59 }

——written by Lyon