UVA - 11174 Stand in a Line

题意：村民排队，村子里有n个人，有多少种方法可以把他们排成一列，使得没有人排在他的父亲前面，输出方案mod 1000000007

思路：一篇概述的不错的博客：点击打开链接，主要是学到的除法求模的定理：

  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\n",ans);
    }   
    return 0;
}

UVA - 11174 Stand in a Line

原文：http://blog.csdn.net/u011345136/article/details/19174453