组合数学的题，求给定结点数可以构造出多少不同的根树。
我的做法跟网上其他的做法有点不同，我是用整数划分的方法将一种结点数的子结点全部分解，然后用乘法原理求出组合数是多少。刚开始的时候忘记处理重复子树的会出现交换以后相同的状况，然后通过推理，发现了重复的个数跟组合数有关，所以开始的时候可以用杨辉三角构造组合数。
例如，如果有n个结点的子树种类有k种，同时有这样的m棵子树，那么这几棵子树的组合数就是Σ((k - i) * C(i + m - 2, m - 2))(0 <= i < k)。然后通过一个深度优先搜索每一种划分的情况，最后就可以得出组合的总数了。
代码如下；
View Code 1 #include2 #include 3 #include 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 #endif103 104 return 0;105 }
yuan神的做法：
模仿yuan神打了一个代码，关键的地方在于重复集合的组合：
引用：由于子树不分顺序，所以枚举出来的相同规模的子树是一种有重集的组合 ，用公式C(n+m-1,m)
View Code 1 #include2 #include 3 #include 4 #include 5 #include 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