学步园

题意是：

村子里有n个人，有多少种方式可以把他们排成一列，使得没人会排在他父亲的前面

然后给的关系大概是一个森林的样子

看训练指南中的讲解才豁然开朗

设f(i)是以节点i为根的子树的排列方法数

则 f(i) = f(c1)* f(c2) *f(c3) * f(c4).....* f(ck) * (s(i) - 1)! / ((s(c1)! * (s(c2))! .... * (s(ck))!)

s(i)表示的是以i为根的子树的节点个数

c1, c2,...ck为i的儿子们

这个式子首先是把各个子树的都排列好

然后子树之间，就类似有重复元素的全排列

然后观察这个式子

将每个非根节点带入上式子

可发现每个非根节点u以(s(u) - 1)!的形式出现在分子一次

以s(u)的形式出现在分母一次。

约分后相当于分子为1,分母为s(u)

得到最终的式子是、

f(root) = (s(root)-1)!/(s(i) * s(2) *... *s(n))

注意原图是个森林

所以我们可以建立一个超级祖先，将所有的根连上去

就成了一个根了

那么其实最终的解就是

n!/(s(1) * s(2) * ... * s(k))

那么因为我们要mod一个数

所以就要边算逆元边mod了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define INF 111111111
#define MAXN 40005
#define MAXM 900005
using namespace std;
long long mod = 1000000007;
long long fac[MAXN];
vector<int>g[MAXN];
int son[MAXN];
int sz[MAXN];
int n, m;
long long fastmod(long long a, long long b, long long c)
{
    long long ret = 1;
    a %= c;
    for(; b; b >>= 1, a = (a * a) % c)
        if(b & 1)
            ret = ret * a % c;
    return ret;
}
void dfs(int u)
{
    sz[u] = 1;
    for(int i = 0; i < g[u].size(); i++)
    {
        dfs(g[u][i]);
        sz[u] += sz[g[u][i]];
    }
}
int main()
{
    fac[0] = 1;
    for(int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * (long long)i % mod;
    int T, u, v;
    scanf("%d", &T);
    while(T--)
    {
        memset(son, 0, sizeof(son));
        scanf("%d%d", &n, &m);
        for(int i = 0; i <= n; i++) g[i].clear();
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &u, &v);
            son[u] = 1;
            g[v].push_back(u);
        }
        for(int i = 1; i <= n; i++)
        {
            if(!son[i])
                dfs(i);
        }
        long long ans = fac[n];
        for(int i = 1; i <= n; i++)
        {
            long long k = fastmod(sz[i], mod - 2, mod);
            ans = ans * k % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}