题意：村子里有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#include #include /*组合+除法的求模题意： 村子里有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 son[maxn]; //存储儿子节点int num[maxn]; //存储以i为根的子树的节点个数，包括节点iint n,m;long long sum; //求(s(1) * s(2) *... *s(n))//快速幂，求sum^(mod-2)%modlong 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