UVA - 11174 Stand in a Line

题意:村民は并んで、村の中でn人がいて、どれだけの方法が彼らを1列に并べることができて、彼の父の前に并ぶ人がいないようにして、方案mod 100000007を出力します
構想:1篇の概説の悪くないブログ:クリックしてリンクを開けて、主に学んだ除法の型を求める定理です:
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 <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 40005;
const long long mod = 1000000007;

vector<int> son[MAXN];
int num[MAXN],n,m;
long long fa[MAXN],f[MAXN];
long long sum;

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();
        }
        memset(fa,0,sizeof(fa));
        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;
        }
        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;
}