「JZOJ5417」合影 - 树形动规

题目大意

    经过一天的忙碌，志愿者们结束了他们的工作，准备站在一排合影留念。
    现在总共有$n$名志愿者留下来准备合影。不过，进程并不是那么顺利，有些同学提出了一些奇奇怪怪的要求（每个人最多只会提出一个）：他必须站在另外一个同学的左边（不一定相邻），仁慈的老师满足了他们的要求。这时，其中一位来自11班的同学小Z陷入了沉思：总共有多少种不同的合法方案数呢？（两种方案不同当且仅存在至少一名同学他在这两个方案当中站的位置不同。）小Z很快就算出来了，于是就把自己的这个问题告诉了好朋友小C。不过，由于小C的数学功底不足，小Z只要求他算出这个答案模质数$p$的余数就可以了。可就算这样，小C也不会做。为了显示自己的水平很高（实际上很低），他找到了你，并把你得出的答案报给小Z，所以你可一定要算对啊！

---

题目分析

注意题目的限制条件构成一棵树，因此这就是一个简单的融合组合数的树形动规。
和保镖排队类似，注意判环。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=200005;
int t,n,m,Size[maxn],InDegree[maxn];
LL f[maxn],fac[maxn],inv[maxn],mod;
bool bj=0,vst[maxn];
vector<int>edges[maxn];

void Clear() {
	memset(InDegree,0,sizeof(InDegree));
	memset(vst,0,sizeof(vst));
	bj=0;
	for(int i=0; i<=n; i++)edges[i].clear();
}

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void Dfs(int Now) {
	vst[Now]=1;
	for(int i=0; i<edges[Now].size(); i++) {
		int Next=edges[Now][i];
		if(vst[Next]) {
			bj=1;
			return;
		}
		Dfs(Next);
		if(bj)return;
	}
}

LL C(LL a,LL b) {
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}

void TreeDp(int Now) {
	f[Now]=1;
	Size[Now]=0;
	for(int i=0; i<edges[Now].size(); i++) {
		int Next=edges[Now][i];
		TreeDp(Next);
		Size[Now]+=Size[Next];
		f[Now]=f[Now]*C(Size[Now],Size[Next])%mod*f[Next]%mod;
	}
	Size[Now]++;
}

LL Quick_Pow(LL a,LL b) {
	LL ans=1;
	while(b) {
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

int main() {
	t=Get_Int();
	while(t--) {
		n=Get_Int();
		m=Get_Int();
		mod=Get_Int();
		Clear();
		fac[0]=inv[0]=1;
		for(int i=1; i<=n+1; i++)fac[i]=fac[i-1]*i%mod;
		inv[n+1]=Quick_Pow(fac[n+1],mod-2);
		for(int i=n; i>=1; i--)inv[i]=inv[i+1]*(i+1)%mod;
		for(int i=1; i<=m; i++) {
			int x=Get_Int(),y=Get_Int();
			AddEdge(y,x);
			InDegree[x]++;
		}
		for(int i=1; i<=n; i++)
			if(!InDegree[i])AddEdge(0,i);
		for(int i=0; i<=n; i++)
			if(!vst[i])Dfs(i);
		if(bj) {
			puts("0");
			continue;
		}
		TreeDp(0);
		printf("%lld\n",f[0]);
	}
	return 0;
}