UVA 11174 - Stand in a Line （数学基础+除法取模） - c++编程基础

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 noperson stands closer to the front of the line than his father. You are giventhe 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 containsT (T<14) the number of test case. Then following lines contains T Testcases.

Each test case starts with 2integers n (1≤n≤40000) and m (0≤m

Output

For each test case the outputcontains a single line denoting the number of different ways the soldier canstand 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 forSample Input

3 2

2 1

3 1

3 0

3 1

2 1

Problemsetter: Abdullah-al-Mahmud

Special Thanks: Derek Kisman

村名排队问题。n个人排成一列，没有人站在他父亲前面的方法数。

这一题主要还是组合数学的问题，

公式就是，n!/(cnt[1]*cnt[2]*....cnt[n) cnt[i]为i的子树的大小

用到除法求模，求逆元

#include   
#include   
#include   
using namespace std;  
  
const int mod=1000000007;  
const int maxn=40000;  
int n,m,cnt[maxn+10];  
long long fact[maxn+10];  
vector  > v;  
  
void ini(){  
    fact[0]=1,fact[1]=1;  
    for(int i=2;i<=maxn;i++){  
        fact[i]=(fact[i-1]*i)%mod;  
    }  
}  
  
void initial(){  
    for(int i=0;i<=n;i++){  
        cnt[i]=-1;  
    }  
    v.clear();  
}  
  
void input(){  
    int x,y;  
    v.resize(n+1);  
    while(m-- >0){  
        scanf("%d%d",&x,&y);  
        v[y].push_back(x);  
    }  
}  
  
int dfs(int x){  
    if(cnt[x]!=-1) return cnt[x];  
    int c=1;  
    for(int i=0;i0){  
        scanf("%d%d",&n,&m);  
        initial();  
        input();  
        computing();  
    }  
    return 0;  
}