UVA 11174 - 조합 수학 + 조합 수 취 모 + dfs

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34531
제목: 
n 개인 과 일부 부자 관 계 를 제시 하고 이 n 개인 에 대해 하나의 배열 을 요구 하 며 그 중에서 아버 지 는 반드시 아들 의 앞 에 서 야 한다.모두 몇 가지 배열 방식 이 있 느 냐 고 물 었 다.
일부 아버지 가 없 는 사람 은 그 가 조상 이라는 것 을 나타 낸다.
모든 조상 노드 에 대해 우 리 는 그 를 뿌리 로 하 는 나무 내부 에서 요구 하 는 합 법 적 인 정렬 방안 을 S [1] 로 한다. 그래서 우 리 는 S [2], S [3] 를 얻 었 다.
모든 나무 에 총 노드 수 는 num [1], num [2]... num [k] 로 기록 합 니 다.
모든 나무 에 대해 그들 사이 의 노드 는 영향 을 주지 않 고 서로 삽입 할 수 있다.
마지막 으로 구 하 는 것 은 길이 가 n 인 서열 이다.
ans=1;
첫 번 째 나무 에 대해 서 는 ans=ans* C(N,num[1])*S【1】;//n 개의 위치 에서 num [1] 개의 위 치 를 선택 하고 이 나 무 를 놓 는 s [1] 가지 방안 을 나타 낸다.
마찬가지 로 두 번 째 나무 에 대해 서 는 ans=ans* C(N-num[1],num[2])*S【2】;//남 은 N - num [1] 개의 위 치 를 num [2] 개의 위치 로 선택 하고 이 나 무 를 놓 는 s [2] 가지 방안 을 나타 낸다.
.......
그럼 요구 하 는 건 num [], S [], 그리고 하나의 조합 수
num 에 대해 dfs 로 루트 노드 를 한 번 검색 하면 됩 니 다. (점 마다 검색 할 필요 가 없습니다. TLE 를 할 수 있 습 니 다. 루트 노드 만 검색 하면 됩 니 다)
S [] 에 대해 서도 dfs 입 니 다. 하위 트 리 의 내부 정렬 방안 수 를 계산 하 는 방법 은 마지막 으로 모든 하위 트 리 간 의 답 [빨간색 글꼴 부분] 을 계산 하 는 것 과 같 습 니 다.
조합 수 에 대해 모델 은 하나의 소수 이기 때문에 직접 역 원 으로 조합 계산 중의 계승 상 제 부분 을 계산 하면 된다.
ac 코드:

 <pre name="code" class="cpp">#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
const long long mod =1000000007;

long long fast_m(long long a,long long b)
{
    long long x,ans=1;
    x=a;
    while(b)
    {
        if (b&1)
            ans=(ans*x)%mod;
        x=(x*x)%mod;
        b/=2;
    }
    return ans;
}
long long fac[40005];							//     
long long cal(long long x,long long y)			//     
{
    long long ans=1;
    ans*=(fac[x]*fast_m(fac[y]*fac[x-y]%mod,mod-2))%mod;
	
    //(a/b)%mod，   (a*b^(mod-2))%mod  mod     
    return ans%mod;
}
vector<long long> tm[40005];		//    i     
long long total[40005]; //	   i            
int vis[40005];			//vis[i]=1           【     】
long long an[40005];	//    i     ,               	 
long long dfs(long long x);				// an    

long long cal_son(long long x);			// total     
int main()
{
	long long i;
    fac[0]=1;

	for(  i=1;i<=40000;i++)
		fac[i]=fac[i-1]*i%mod;
 
	 	int t;
	cin>>t;
	   while(t--)
	   {
		    memset(an,0,sizeof(an)); 
		   memset(vis,0,sizeof(vis));

		   long long n,m;
		   scanf("%lld%lld",&n,&m);
		   for (i=1;i<=n;i++)
			   tm[i].clear();
		   
		   long long tmp,fa;
		   
		   for (i=1;i<=m;i++)
		   {
			   scanf("%lld%lld",&tmp,&fa);
			   tm[fa].push_back(tmp);
			   vis[tmp]=1;//   tmp    
		   }
		   
		   for (i=1;i<=n;i++)
		   { 
			   if (vis[i]) continue;
			   if (tm[i].size())
			   { 
				    cal_son(i) ;		//          【     】
			   }
			   else
					total[i]=1;			//     
		   }
		    for (i=1;i<=n;i++)
		   {
			   if (vis[i]) continue;		//   
			   if (tm[i].size())		
				   dfs(i);				//            
		   }
		   
		   long long ans=1;
		   long long tmp_n=n;
		   for (i=1;i<=n;i++)
		   {
			   if (vis[i]) continue;//     
			   ans=ans*cal(tmp_n,total[i])%mod;		
			   tmp_n-=total[i]; //      ..     n ,    RE    
			  if (an[i])      //           ,        
			   ans=ans*an[i]%mod;
		   }
		   printf("%lld
",ans%mod);
	   }
	   return 0;
}

long long dfs(long long x)
{
  
	long long ans=1,i;
	for (i=0;i<tm[x].size();i++)
	{
		long long tt=tm[x][i];
		if (tm[tt].size())
		{ 
				dfs(tt);  //RE   ,  dfs(i)    
		}
	}
	 
	 long long sum=total[x]-1;
		for (i=0;i<tm[x].size();i++)
		{
			long long num=tm[x][i];
			long long tt=total[num]; 
			ans=ans*cal(sum,tt)%mod;
			if (an[num])
			ans=ans*an[num]%mod;
			sum-=tt;
		}
		

	 
	return an[x]=ans%mod;
}
 
long long cal_son(long long x)
{
	int son=0;
	son+=tm[x].size();
	int i;
	for (i=0;i<tm[x].size();i++)
	{
	
		long long tt=tm[x][i];
		if (tm[tt].size())
		{
		son+=cal_son(tt);  //RE   ,  dfs(i)   
		}
		else
		{
			total[tt]=1;
		}
	}
	total[x]=son+1;  //    
	return son;
return 0;
}