Stand in a Line UVA11174

すべての村人を一列に並べて、すべての父はその子孫の前に並ばなければなりません.ある人の父は村にいません.並べた総数を求めます.
まず仮想ノード0を設定し、すべての父親が村にいない人が仮想父親であることを示し、すべての点が木を構成します.
iをルートとするサブツリーの配列数をf(i)とし,そのノード数をs(i)とし,
Cを根とする1本の子木を考え,cjをその子とし,まず各子ノードを根とする子木の配列は互いに独立して乗算原理を満たすため,子木間の配列を考慮しない場合の配列総数は∏f(cj)となり,すべての子孫が挿入される(その中で1本の子木の子孫の相対的な位置は変わらない)配列数を考え,これは繰り返し要素の全配列に相当するので、f(C)=f(c 1)*f(c 2)...f(cj)*(s(C)-1)!/(s(c1)!s(c2)!...s(cj)!),再帰式の解によりf(root)=(s(root)−1)に簡略化できる!/(s(1)s(2)...s(n),(訓練マニュアルで与えられた式に問題がある),この問題では100000007型取りの結果に対する答えを求め,除算をその逆元に乗じたものに変換するので,前処理は1から40000階乗とその⊙mでの乗算逆元,m=100000007であり,与えられたデータに従って持ち込めばよい.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>   
#include <map>
#include <string>  
#include <climits> 
#include <set>
#include <string> 
#include <sstream>
#include <utility>   
#include <ctime>
 
using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::make_pair;
using std::greater;
using std::endl;

typedef long long LL;
const int MAXN(40010);
const LL MOD(1000000007);

void egcd(LL a, LL b, LL &x, LL &y, LL &G)
{
	if(!b)
	{
		G = a;
		x = 1;
		y = 0;
	}
	else
	{
		egcd(b, a%b, y, x, G);
		y -= x*(a/b);
	}
}

LL inverse(LL a, LL M)
{
	LL x, y, G;
	egcd(a, M, x, y, G);
	return G == 1? (x+M)%M: -1LL;
}

LL fac[MAXN], inv[MAXN];
struct EDGE
{
	int v;
	EDGE *next;
};

EDGE *first[MAXN];
EDGE edge[MAXN];
EDGE *rear;

void init()
{
	memset(first, 0, sizeof(first));
	rear = edge;
}

void insert(int tu, int tv)
{
	rear->v = tv;
	rear->next = first[tu];
	first[tu] = rear++;
}

bool is_root[MAXN];
LL ans;

int dfs(int cur)
{
	int ts = 1;
	for(EDGE *i = first[cur]; i; i = i->next)
		ts += dfs(i->v);
	if(cur != 0)
		ans = ans*inv[ts]%MOD;
	return ts;
}
	
int main()
{
	fac[0] = 1LL;
	for(int i = 1; i <= 40000; ++i)
	{
		fac[i] = fac[i-1]*i%MOD;
		inv[i] = inverse(i, MOD);
	}
	int T;
	scanf("%d", &T);
	while(T--)
	{
		init();
		int n, m;
		scanf("%d%d", &n, &m);
		int tu, tv;
		memset(is_root, -1, sizeof(is_root));
		for(int i = 0; i < m; ++i)
		{
			scanf("%d%d", &tv, &tu);
			insert(tu, tv);
			is_root[tv] = false;
		}
		for(int i = 1; i <= n; ++i)
			if(is_root[i])
				insert(0, i);
		ans = fac[n];
		dfs(0);
		printf("%lld
", ans);
	}
	return 0;
}