依旧是《训练指南》上的一道例题。书上讲的比较抽象，下面就把解法具体一下。因为涉及到父子关系，因此自然而然可以将n个节点构造成一棵树，最后将形成一个森林。接下来将使用递归的手法。设f(i)是以节点i为树根的子树，节点i有儿子c1,c2,c3….cj共j棵子树。s[i]为树根为i的子树包含的节点数。如果分别先给各个子树内部排序，那么毫无疑问，
共有f(c1)*f(c2)*f(c3)….*f(cj)种情况。接下来又要将所有子树的节点排成一个序列。那么我们事先不考虑各个子树的内部排序，共有(s[i]-1)!/(s[c1]!*s[c2]!*…..s[cj]!种情况。最后，我们将两种情况合起来，就是f(i)的解了，为f(c1)*f(c2)….*f(cj)*(s[i]-1)!/(s[c1]!*s[c2]!*…..s[cj]!)中情况。
事实上，接下来还可以进一步化简，设c1有孩子节点x1,x2,x3….xk。那么f(c1)=f(x1)*f(x2)…..f(xk)*(s[c1]-1)!/(s[x1]!*x[x2]!….*x[xk]!)。将f(c1)代入，分子中的(s[c1]-1)!和分母中的s[c1]!约分的s[c1]，然后依次类推，最后分母必然会化为s[1]*s[2]*s[3]…s[n]。因为总共n个节点构成一个森林，，因此s[root](root可能为虚拟树根)为n+1,那么最后分母为n!。最后，求出n!/(s[1]*s[2]…s[n])就是我们要求的解。
还要注意的是，最后模运算的时候，1的逆为1。
#include <iostream>#include <cstdio>#include <vector>#include <cstring>#define MAX 40000+5#define MOD 1000000007#define LL long longusing namespace std;LL fac[MAX],N[MAX];//fac[i]为i!,N[i]为i关于MOD的逆int T,n,m;int s[MAX],vis[MAX];vector<int> Tree[MAX];LL inv(LL a,LL n);void gcd(LL a,LL b,LL& d,LL& x,LL& y);int dfs(int);int main(){freopen("data.txt","r",stdin);fac[0]=fac[1]=N[1]=1;//注意1的逆为1for(LL i=2;i<MAX;++i){fac[i]=(i*fac[i-1])%MOD;N[i]=inv(i,MOD);}cin>>T;while(T–){cin>>n>>m;memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i) Tree[i].clear();for(int i=0;i<m;++i){int a,b;cin>>a>>b;Tree[b].push_back(a);}for(int i=1;i<=n;++i){//DFS统计每棵子树包含的节点数if(!vis[i]) dfs(i);}LL ans=fac[n];for(int i=1;i<=n;++i){ans=(ans*N[s[i]])%MOD;}cout<<ans<<endl;}return 0;}LL inv(LL a,LL n)//求逆运算，参考《训练指南》{LL d,x,y;gcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}void gcd(LL a,LL b,LL& d,LL& x,LL& y)//扩展欧几里得算法{if(!b){d=a;x=1;y=0;}else{gcd(b,a%b,d,y,x);y-=x*(a/b);}}int dfs(int r){int num=0;for(int i=0;i<Tree[r].size();++i){num+=dfs(Tree[r][i]);}vis[r]=1;s[r]=num+1;return s[r];}
生命中,每一种苦难的背后都有一片晴朗的天空
