题意：村子里有n个人，给出父亲和儿子的关系，有多少种方式可以把他们排成一列，使得没人会排在他父亲的前面
思路：设f[i]表示以i为根的子树有f[i]种排法，节点i的各个子树的根节点，即它的儿子为c1,c2,c3...ck。
那么先给节点i的子树确定各自的顺序，为f(c1),f(c2)...f(ck)。
然后把每棵子树的所有节点看成同一元素，根据有重复元素的全排列方式共有s(i-1)!/(s(c1)!*s(c2)!*...*s(ck)!)
再根据乘法原理，f[i]=f(c1)* f(c2) *f(c3) * f(c4).....* f(ck) * (s(i) - 1)! / ((s(c1)! * (s(c2))! .... * (s(ck))!) 其中，s[i]表示以i为根的子树的节点个数。
然后观察这个式子，将每个非根节点带入上式子，可发现每个非根节点u以(s(u) - 1)!的形式出现在分子一次，以s(u)!的形式出现在分母一次。
约分后相当于分子为1,分母为s(u)，得到最终的式子是： f(i) = (s(i)-1)!/(s(1) * s(2) *... *s(k)) （1,2,3...k为以i为根的子树的所有节点，不包括i）
这样，我们可以设立一个虚父节点root=0，把森林连接起来成为一棵树，这样所求的答案即为： f(root) = (s(root)-1)!/(s(1) * s(2) *... *s(n))
但是最后要让我们求模，而式子中有除法，所以要用到以下定理： a = (b/c) ==> a%m = b*c^(m-2)%m ( m为素数 )
证明如下： b = a * c 根据费马小定理 a^(p-1)= 1 %p (p是素数且a不能整除p) 所以 c^(m-1)%m=1%m
因此 a % m = a*1%m = a * c^(m-1)%m = a*c*c^(m-2)%m = b*c^(m-2)%m;
#include <iostream> #include <stdio.h> #include <vector> /* 组合+除法的求模 题意： 村子里有n个人，给出父亲和儿子的关系，有多少种方式可以把他们排成一列，使得没人会排在他父亲的前面 思路： 设f[i]表示以i为根的子树有f[i]种排法，节点i的各个子树的根节点，即它的儿子为c1,c2,c3...ck。 那么先给节点i的子树确定各自的顺序，为f(c1),f(c2)...f(ck)。 然后把每棵子树的所有节点看成同一元素，根据有重复元素的全排列方式共有s(i-1)!/(s(c1)!*s(c2)!*...*s(ck)!) 再根据乘法原理，f[i]=f(c1)* f(c2) *f(c3) * f(c4).....* f(ck) * (s(i) - 1)! / ((s(c1)! * (s(c2))! .... * (s(ck))!) 其中，s[i]表示以i为根的子树的节点个数。 然后观察这个式子，将每个非根节点带入上式子，可发现每个非根节点u以(s(u) - 1)!的形式出现在分子一次，以s(u)!的形式出现在分母一次。 约分后相当于分子为1,分母为s(u)，得到最终的式子是： f(i) = (s(i)-1)!/(s(1) * s(2) *... *s(k)) （1,2,3...k为以i为根的子树的所有节点，不包括i） 这样，我们可以设立一个虚父节点root=0，把森林连接起来成为一棵树，这样所求的答案即为： f(root) = (s(root)-1)!/(s(1) * s(2) *... *s(n)) 但是最后要让我们求模，而式子中有除法，所以要用到以下定理： a = (b/c) ==> a%m = b*c^(m-2)%m ( m为素数 ) 证明如下： b = a * c 根据费马小定理 a^(p-1)= 1 %p (p是素数且a不能整除p) 所以 c^(m-1)%m=1%m 因此 a % m = a*1%m = a * c^(m-1)%m = a*c*c^(m-2)%m = b*c^(m-2)%m; */ using namespace std; const long long mod=1000000007; const int maxn=40005; vector<int> son[maxn]; //存储儿子节点 int num[maxn]; //存储以i为根的子树的节点个数，包括节点i int n,m; long long sum; //求(s(1) * s(2) *... *s(n)) //快速幂，求sum^(mod-2)%mod long long quickPow(long long a,long long b){ long long ans=1; while(b){ if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b=b>>1; } return ans; } //预处理求阶乘 void init(){ f[0]=1; for(int i=1;i<maxn;i++){ f[i]=(f[i-1]*i)%mod; } } //递归计算子树的节点个数 int dfs(int u){ if(son[u].empty()){ num[u]=1; return num[u]; } int v; for(int i=0;i<son[u].size();i++){ v=son[u][i]; num[u]+=dfs(v); } num[u]++; return num[u]; } int main() { int t,a,b; long long ans; init(); scanf("%d",&t); while(t--){ for(int i=0;i<=n;i++){ num[i]=0; son[i].clear(); } scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&a,&b); son[b].push_back(a); fa[a]=b; } //设立虚父节点0 for(int i=1;i<=n;i++){ if(!fa[i]){ son[0].push_back(i); } } dfs(0); sum=1; for(int i=1;i<=n;i++) sum=(sum*num[i])%mod; ans=(f[n]*quickPow(sum,mod-2))%mod; printf("%lld ",ans); } return 0; }