uva 11174 Stand in a Line （排列组合）

　　训练指南的题目。

　　题意是，给出n个人，以及一些关系，要求对这n个人构成一个排列，其中父亲必须排在儿子的前面。问一共有多少种方式。

　　做法是，对于每一个父节点，将它的儿子结点构成的子树看成无序状态，这样子对当前父节点整棵树计算一个排列数。如果把所有的这样的式子写出来，可以发现分子分母是可以相消的。假设点的总数是S，儿子的点的数目分别是A,B,C...，这样的话，对于这个结点，可以求得F(S)=F(A)+F(B)+F(C)+...。最后的结果是所有子树的F(S)*F(A)*F(B)*F(C)*...。最后消去以后就只剩下F(S)/(c(A)*c(B)*c(C)*...)，其中c(X)是结点X的子树的结点个数。

代码如下：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <map>
 6 #include <vector>
 7 
 8 using namespace std;
 9 
10 const int N = 44444;
11 map<int, int> id;
12 int lsf[N], pn, prm[N >> 3];
13 
14 void getprm() {
15     id.clear();
16     lsf[0] = lsf[1] = 1;
17     pn = 0;
18     for (int i = 2; i < N; i++) {
19         if (!lsf[i]) {
20             id[i] = pn;
21             prm[pn++] = i;
22             for (int j = i; j < N; j += i) lsf[j] = i;
23         }
24     }
25 }
26 
27 typedef long long LL;
28 const LL MOD = 1000000007;
29 int cnt[N], fcn[N];
30 bool vis[N], fa[N];
31 vector<int> rel[N];
32 
33 LL multi(int a, int b) {
34     LL ret = 1, p = a;
35     while (b > 0) {
36         if (b & 1) ret *= p, ret %= MOD;
37         p *= p, p %= MOD;
38         b >>= 1;
39     }
40     return ret;
41 }
42 
43 void dfs(int x) {
44     cnt[x] = 1;
45     for (vector<int>::iterator vi = rel[x].begin(); vi != rel[x].end(); vi++) {
46         dfs(*vi);
47         cnt[x] += cnt[*vi];
48     }
49 }
50 
51 int main() {
52     getprm();
53     int n, m, T;
54     scanf("%d", &T);
55     while (T-- && ~scanf("%d%d", &n, &m)) {
56         memset(vis, 0, sizeof(vis));
57         memset(cnt, 0, sizeof(cnt));
58         memset(fcn, 0, sizeof(fcn));
59         memset(fa, 0, sizeof(fa));
60         int x, y;
61         for (int i = 0; i <= n; i++) rel[i].clear();
62         while (m--) {
63             scanf("%d%d", &x, &y);
64             rel[y].push_back(x);
65             fa[x] = true;
66         }
67         for (int i = 1; i <= n; i++) if (!fa[i]) rel[0].push_back(i);
68         dfs(0);
69         for (int i = 1; i <= n; i++) {
70             int t = i;
71             while (t > 1) {
72                 fcn[id[lsf[t]]]++;
73                 t /= lsf[t];
74             }
75             t = cnt[i];
76             while (t > 1) {
77                 fcn[id[lsf[t]]]--;
78                 t /= lsf[t];
79             }
80             //cout << "~~ " << i << ' ' << cnt[i] << endl;
81             //for (int i = 0; i < 10; i++) cout << prm[i] << ' ' << fcn[i] << endl;
82         }
83         //cout << pn << endl;
84         LL ans = 1;
85         for (int i = 0; i < pn; i++) {
86             ans *= multi(prm[i], fcn[i]);
87             ans %= MOD;
88         }
89         cout << ans << endl;
90     }
91     return 0;
92 }

View Code

——written by Lyon　　