題意：

有 \(n\) 個人排成一排，每個點 \(i\) 最多會給出一條限制，形如 \((i,j)\) 表示點 \(i\) 必須站在 \(j\) 的左側。問有多少種成立的方案數，答案對輸入的模數 \(p\) 取模。

對于\(100\%\) 的數據：\(n≤2\times 10^5,m≤2\times 10^5,m≤n,n+10≤p≤10^9+7,T≤10\).

題解：

給個不一樣的做法，應該好寫一點。

我們考慮限制構成什么，先用限制構造邊 \(i\to j\)，發現如果所有 \(i\) 都有出邊那么這玩意會構成外向基環樹森林，但是我們會發現如果有環，那一定無解，所以在有解的情況下會構成一棵樹。

現在再思考限制的本質，對于 \(i\to j\)， 這是一個經典的問題，等價于滿足構成的樹上 \(i\) 的拓撲序小于 \(j\)。

對于這個經典的有根樹版本問題我們有一個經典的結論：

其中 \(siz_i\) 為 \(i\) 的子樹大小。考慮怎么把我們的限制構造成有根樹，發現我們把 \(i\to j\) 都換成 \(j\to i\) 答案肯定是不變的，把題意理解成 \(i\) 在 \(j\) 的右側即可。這樣一定是有根樹。

證明：

考慮一般情況，若發現如果所有 \(i\) 都有出邊那么這玩意會構成內向基環樹森林。考慮刪掉環的一些部分使得有答案，那么你一定可以找到一個根在環上一點。

那么直接做就可以了。時間復雜度 \(O(Tn)\).

細節：預處理逆元可以做到線性，這里還有一個性質值得注意，數據范圍里寫了 \(n+10\le p\)，這使得我們可以直接處理逆元，因為如果 \(n\ge p\) 的話我們就要用 \(lucas\) 定理了。

code：

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define m(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=2e5+10;
int n,m,k,T,siz[N],vis[N],cnt,tg,mod,ni[N],ans;
vector<int> g[N];
int ksm(int x,int k){
	int ans=1;
	while(k){
		if(k&1) ans=ans*x%mod;
		x=x*x%mod;k>>=1;
	}return ans;
}
void dfs(int u){
	vis[u]=cnt;siz[u]=1;
	for(int v:g[u]){
		if(vis[v]==cnt){
			tg=1;break;	
		}else if(!vis[v]) dfs(v);
		siz[u]+=siz[v];
	}
}
void init(){
	rep(i,1,n) g[i].clear();tg=0;
	cnt=0;m(siz);m(vis);ni[1]=1;ans=1;
	rep(i,2,n) ni[i]=(-mod/i*ni[mod%i]%mod+mod)%mod;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>T;while(T--){
		cin>>n>>m>>mod;init();
		rep(i,1,m){
			int x,y;cin>>x>>y;
			g[y].pb(x);
		}rep(i,1,n){
			if(!vis[i]) cnt++,dfs(i);
		}if(tg==1){cout<<0<<'\n';continue;}
		rep(i,1,n){ans=ans*i%mod;
			ans=ans*ni[siz[i]]%mod;
		}cout<<ans<<'\n';
	}
	return 0;
}

官方解法：

算法1

對于 15%的數據 我們可以直接枚舉所有置換，再進行判斷即可，時間復雜度$ O(T*n!）$

算法2

對于 50%的數據 定義$ f[S]$表示已經選了元素集合為 \(S\) 的合法方案數是多少， 轉移方程為 \(f[S]=∑ ??[?? ? 2^x ]\)，滿足 x 是 S 中的元素且所有限制 均不矛盾，可以先預處理每個位置不合法狀態的集合，這樣 時間復雜度 \(O（n T *2^n）\),如果你寫成 \(O（n*n*T*2^n）\)，那么 恭喜你，你只有 30（常數小的除外）分了。

算法3

對于余下所有數據, 我們需要觀察出一些性質。
如果我們對于一條限制 \((x, y)\), 建一條 \(x->y\) 的邊, 就會發 現在這張圖中每個點的出邊最多只有一條。

如果在這張圖中有環, 則答案一定為 0 。
如果這張圖無環, 則這些邊一定構成一個森林。
所以我們可以跑樹形 dp。

定義 \(f[i]\) 表示第 \(i\) 棵子樹的方案數是多少。
轉移時, 相當于有很多的兒子 \(s_{1}, s_{2} \ldots s_{n}\) (設每個兒子的子樹 大小為 size）, 相當于對于一個序列中, 先選 1 個位置給 \(s_{1}\),
再在余下的位置中, 選 2 個位置給 \(s_{2} \ldots\), 相當于一些組合數的 乘積再乘以每個兒子內部的方案數。

算法4

對于 \(70 \%\) 的數據

我們可以利用組合恒等式 \(c_{x}^{y}=c_{x-1}^{y}+C_{x-1}^{y-1}\) 預處理組合數, 或是預 處理逆元暴力求組合數, 復雜度均為 \(O\left(T^{*} n * n\right)[m\) 一定小 于等于 \(n\), 所以 \(m\) 近似為 \(n\) ]

算法5

對于 \(100 \%\) 的數據

我們可以先預處理階乘, 階乘的逆元, 然后組合數就可以 \(\mathrm{O}(1)\) 了, 總復雜度為 \(O\left(T^{*}(n+m)\right)\)