Stand in a Line
大意：有n个人排队，问有多少种排列使得没有人排在他的父亲前面
不难发现这是一个森林
设一个虚根root把所有树的根连起来，root排在所有方案的最前面，总方案数不变
设i的儿子为son1(i),son2(i)....sonk(i),k位i儿子的数量
设size【i】为i这棵子树的节点个数
f【i】为i这颗子树的方案数
f【i】 = f【son1【i】】 f【son2【i】】 ... f【sonk【i】】 (size【i】 - 1) / (size【son1【i】】! size【son2【i】】! .. size【sonk【i】】!)
相当于每颗子树内部排列：f【son1【i】】 f【son2【i】】 ... f【sonk【i】】
然后把同一颗子树看做相同的排：(size【i】 - 1) / (size【son1【i】】! size【son2【i】】! .. size【sonk【i】】!)
把f【son1【i】】...f【sonk【i】拆开，带进去
发现size【i】！作为分母出现一次，（size【i】-1）!作为分母出现一次，约分得size【i】
于是f【root】 = (size【root】 - 1)!/(size【son1【i】】 size【son2【i】】 ... size【sonk【i】】)
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #define min(a, b) ((a) < (b) ? (a) : (b))
10 #define max(a, b) ((a) > (b) ? (a) : (b))
11 #define abs(a) ((a) < 0 ? (-1 (a)) : (a))
12 inline void swap(long long &a, long long &b)
13 {
14 long long tmp = a;a = b;b = tmp;
15 }
16 inline void read(long long &x)
17 {
18 x = 0;char ch = getchar(), c = ch;
19 while(ch < '0' || ch > '9') c = ch, ch = getchar();
20 while(ch <= '9' && ch >= '0') x = x 10 + ch - '0', ch = getchar();
21 if(c == '-') x = -x;
22 }
23
24 const long long INF = 0x3f3f3f3f;
25 const long long MAXN = 100000 + 10;
26 const long long MOD = 1000000007;
27
28 struct Edge
29 {
30 long long u,v,nxt;
31 Edge(long long _u, long long _v, long long _nxt){u = _u;v = _v;nxt = _nxt;}
32 Edge(){}
33 }edge【MAXN [ 1】;
34 long long head【MAXN】, cnt;
35 inline void insert(long long a, long long b)
36 {
37 edge【++cnt】 = Edge(a,b,head【a】);
38 head【a】 = cnt;
39 }
40
41 //代码效果参考：http://www.lyjsj.net.cn/wz/art_23110.html
long long f【MAXN】,t,n,m,b【MAXN】,size【MAXN】,fa【MAXN】;42
43 void dfs(long long u)
44 {
45 size【u】 = 1;b【u】 = 1;
46 for(register long long pos = head【u】;pos;pos = edge【pos】.nxt)
47 {
48 long long v = edge【pos】.v;
49 if(b【v】) continue;
50 dfs(v), size【u】 += size【v】;
51 }
52 return;
53 }
54
55 long long pow(long long a, long long b)
56 {
57 long long r = 1, base = a%MOD;
58 //代码效果参考：http://www.lyjsj.net.cn/wz/art_23108.html
for(;b;b ]= 1)59 {
60 if(b & 1) r = base, r %= MOD;
61 base = base, base %= MOD;
62 }
63 return r;
64 }
65
66 long long ni(long long x)
67 {
68 return pow(x, MOD - 2);
69 }
70
71 int main()
72 {
73 read(t);
74 f【0】 = 1;
75 for(register long long i = 1;i < MAXN;++ i)
76 f【i】 = (f【i - 1】 i) % MOD;
77 for(;t;--t)
78 {
79 memset(fa, 0, sizeof(fa));memset(head, 0, sizeof(head)), memset(b, 0, sizeof(b)), cnt = 0;
80 read(n), read(m);
81 for(register long long i = 1;i <= m;++ i)
82 {
83 long long tmp1,tmp2;
84 read(tmp1), read(tmp2);
85 insert(tmp2, tmp1);
86 fa【tmp1】 = tmp2;
87 }
88 for(register long long i = 1;i <= n;++ i)
89 //代码效果参考：http://www.lyjsj.net.cn/wx/art_23106.html
if(!b【i】)90 {
91 int now = i;
92 while(fa【now】) now = fa【now】;
93 dfs(now);
94 }
95 long long ans = 1;
96 for(register long long i = 1;i <= n;++ i) ans = size【i】, ans %= MOD;
97 printf("%lld\n", f【n】 * ni(ans) % MOD);
98 }
99 return 0;
100 }
UVA11174
