2013-07-12 13:58:10| 人氣373| 回應0 | 上一篇 | 下一篇

[UVA][組合][逆元] 11174 - Stand in a Line

Input

First line of the input contains T (T<14) the number of test case. Then following lines contains T Test cases.

Each test case starts with 2 integers n (1≤n≤40000) and m (0≤m<n). n is the number of people in the byteland and m is the number of people whose father is alive. These n people are numbered 1...n.Next m line contains two integers a and b denoting that b is the father of a. Each person can have at most one father. And no person will be an ancestor of himself.

Output

For each test case the output contains a single line denoting the number of different ways the soldier can stand in a single line. The result may be too big. So always output the remainder on dividing ther the result by 1000000007.

Sample Input Output for Sample Input

3 2

2 1

3 1

3 0

3 1

2 1

Problem setter: Abdullah-al-Mahmud

Special Thanks: Derek Kisman

題目其實就是在求拓樸排序的方法數有幾種。

對於一個根的方法數定義為 f(root), 其下有 s1, s2, ... , sn 編號的子節點。
而定義 S(x) 為 x 以下的所有節點個數(不包括 x)。

f(root) = f(s1)*f(s2)*f(s3)* ... *f(sn) S(root)!/(S(s1)! S(s2)! S(s3)! ... S(sn)!)

逆元計算 n! 在 mod 1000000007 下的值為何，採用費馬小定理計算之。
先將 n! mod 1000000007 再去找逆元。

逆元計算 /n! 相當於乘一個它的逆元。

#include <stdio.h>
#include <vector>
#define MOD 1000000007
using namespace std;
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while(y) {
        if(y&1) ret = ret*x, ret %= mod;
        y >>= 1;
        x = (x*x)%mod;
    }
    return ret;
}
vector<int> g[65536];
long long f[65536] = {1}, vf[65536];
long long dfs(int nd, int &soncnt) {
    soncnt = 0;
    int ss;
    long long ret = 1;
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        ret = (ret*dfs(*it, ss))%MOD;
        ret = (ret*vf[ss])%MOD;
        soncnt += ss;
    }
    ret = (ret*f[soncnt])%MOD;
    soncnt++;
    return ret;
}
int main() {
    int i, j, k;
    int testcase, n, m;
    int son, parent;
    for(i = 1; i < 65536; i++) {
        f[i] = (f[i-1]*i)%MOD;
        vf[i] = mpow(f[i], MOD-2, MOD);
    }
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        int root[65536] = {};
        for(i = 1; i <= n; i++)
            g[i].clear(), root[i] = 1;
        for(i = 0; i < m; i++) {
            scanf("%d %d", &son, &parent);
            g[parent].push_back(son);
            root[son] = 0;

        }
        long long ret = 1;
        int ss, rcnt = 0;
        for(i = 1; i <= n; i++) {
            if(root[i]) {
                ret = (ret*dfs(i, ss))%MOD;
                ret = (ret*vf[ss])%MOD;
            }
        }
        ret = (ret*f[n])%MOD;
        printf("%lld\n", ret);
    }
    return 0;
}

我要檢舉

#11174#Stand in a Line#組合#逆元

台長： Morris

您可能對以下文章有興趣

[UVA][中國郵路問題] 10296 - Jogging Trails

[UVA][雙向BFS] 704 - Colour Hash

[UVA][Math] 11428 - Cubes

[UVA][SCC、Tarjan算法] 11709 - Trust groups

人氣(373) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][greedy] 11158 - Elegant Permuted Sum
此分類上一篇:[UVA] 11155 - Be Efficient

回應(0)