[UVA][組合][逆元] 11174 - Stand in a Line
Problem J
Stand in a Line
Input: Standard Input
Output: Standard Output
All the people in the byteland want to stand in a line in such a way that no person stands closer to the front of the line than his father. You are given the information about the people of the byteland. You have to determine the number of ways the bytelandian people can 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 3 2 2 1 3 1 3 0 3 1 2 1 |
2 6 3
|
Problem setter: Abdullah-al-Mahmud
Special Thanks: Derek Kisman
題目其實就是在求拓樸排序的方法數有幾種。
而定義 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 <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;
}