题意：
有n个人排队，要求每个人不能排在自己父亲的前面(如果有的话)，求所有的排队方案数模1e9+7的值。
分析：
《训练指南》上分析得挺清楚的，把公式贴一下吧：
设f(i)为以i为根节点的子树的排列方法，s(i)表示以i为根的子树的节点总数。
f(i) = f(c1)f(c2)...f(ck)×(s(i)-1)!/(s(c1)!s(c2)!...s(ck)!)
按照书上最开始举的例子，其实这个式子也不难理解，就是先给这些子树确定一下位置，即有重元素的全排列。
子树的位置确定好以后，然后再确定子树中各个节点的顺序。
对了，因为求组合数会用到除法，而且1e9+7又是个素数，所以我们在做除法的时候只要乘上它对应的乘法逆元即可。
这是递归计算的代码：
#include <bits/stdc++.h> using namespace std; const int maxn = + ;
const int MOD = ; vector<int> sons[maxn];
int fa[maxn], fac[maxn], ifac[maxn]; inline int mul_mod(int a, int b, int n = MOD)
{
a %= n; b %= n;
return (int)((long long)a * b % n);
} void gcd(int a, int b, int& d, int& x, int& y)
{
if(!b) { d = a; x = ; y = ; }
else{ gcd(b, a%b, d, y, x); y -= x*(a/b); }
} int inv(int a, int n)
{
int d, x, y;
gcd(a, n, d, x, y);
return d == ? (x+n)%n : -;
} int C(int n, int m)
{ return mul_mod(mul_mod(fac[n], ifac[m]), ifac[n-m]); } void init()
{
fac[] = ifac[] = ;
for(int i = ; i < maxn; i++)
{
fac[i] = mul_mod(fac[i - ], i);
ifac[i] = inv(fac[i], MOD);
}
} int count(int u, int& size)//size是u为根的子树的节点总数
{//统计u为根的子树的排列方案
size = ;
int ans = ;
int d = sons[u].size();
vector<int> sonsize;
for(int i = ; i < d; i++)
{
int sz;
ans = mul_mod(ans, count(sons[u][i], sz));
size += sz;
sonsize.push_back(sz);
}
int sz = size - ;
for(int i = ; i < d; i++)
{
ans = mul_mod(ans, C(sz, sonsize[i]));
sz -= sonsize[i];
}
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); init();
int T;
scanf("%d", &T);
while(T--)
{
int n, m;
scanf("%d%d", &n, &m);
memset(fa, , sizeof(fa));
for(int i = ; i <= n; i++) sons[i].clear();
for(int i = ; i < m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
fa[a] = b;
sons[b].push_back(a);
}
for(int i = ; i <= n; i++)
if(!fa[i]) sons[].push_back(i);
int size;
printf("%d\n", count(, size));
} return ;
}
代码君
书上后面又提到如果将上式完全展开，每个非根节点u都以(s(u)-1)!出现在分子一次，又以s(u)!出现在分母一次，约分后就只剩分母一个s(u)了。
这样f(root) = (s(root)-1)!/(s(1)s(2)...s(n))，又因为s(root) = n+1(因为除了n个人还有一个虚拟的0祖宗节点)，
所以f(root) = n!/(s(1)s(2)...s(n))，还是用递归算出所有的s(i)
这样预处理一下40000以内的阶乘和乘法逆元即可。
#include <bits/stdc++.h> using namespace std; const int maxn = + ;
const int MOD = ; int n, m;
vector<int> sons[maxn];
int fa[maxn], fac[maxn], ifac[maxn], inverse[maxn], sonsize[maxn]; inline int mul_mod(int a, int b, int n = MOD)
{
a %= n; b %= n;
return (int)((long long)a * b % n);
} void gcd(int a, int b, int& d, int& x, int& y)
{
if(!b) { d = a; x = ; y = ; }
else{ gcd(b, a%b, d, y, x); y -= x*(a/b); }
} int inv(int a, int n = MOD)
{
int d, x, y;
gcd(a, n, d, x, y);
return d == ? (x+n)%n : -;
} int C(int n, int m)
{ return mul_mod(mul_mod(fac[n], ifac[m]), ifac[n-m]); } void init()
{
fac[] = ifac[] = ;
for(int i = ; i < maxn; i++)
{
fac[i] = mul_mod(fac[i - ], i);
inverse[i] = inv(i);
}
} void count(int u, int& size)
{//统计以u为根的子树节点个数
size = ;
int d = sons[u].size();
for(int i = ; i < d; i++)
{
int sz;
count(sons[u][i], sz);
size += sz;
}
sonsize[u] += size;
} int main()
{
//freopen("in.txt", "r", stdin); init();
int T;
scanf("%d", &T);
while(T--)
{
memset(fa, , sizeof(fa));
memset(sonsize, , sizeof(sonsize));
for(int i = ; i <= n; i++) sons[i].clear(); scanf("%d%d", &n, &m);
for(int i = ; i < m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
fa[a] = b;
sons[b].push_back(a);
}
for(int i = ; i <= n; i++)
if(!fa[i]) sons[].push_back(i);
int size;
count(, size);
//for(int i = 1; i <= n; i++) printf("%d\n", sonsize[i]);
int ans = fac[n];
for(int i = ; i <= n; i++) ans = mul_mod(ans, inverse[sonsize[i]]);
printf("%d\n", ans);
} return ;
}
代码君