题目分析
有nnn个人站成一排，给出mmm对父子关系(a,b)(a, b)(a,b)，表示bbb是aaa的父亲。要求排列中任何人都不能站在他父亲的前面。求满足条件的排列数，结果对100000000710000000071000000007取模。
约束条件：
- T<14T < 14T<14（测试用例数）
- 1≤n≤400001 \leq n \leq 400001≤n≤40000
- 0≤m<n0 \leq m < n0≤m<n
- 每个人最多有一个父亲
- 不存在祖先环
解题思路
这个问题可以转化为森林的拓扑排序计数问题。父子关系构成一个有向无环图（DAG\texttt{DAG}DAG），且由于每人最多一个父亲，实际上形成的是多棵树（森林）。
关键公式
对于一棵有kkk个节点的有根树，其拓扑排序数量为：
k!∏u∈treesize[u] \frac{k!}{\prod_{u \in \text{tree}} size[u]}∏u∈treesize[u]k!
其中size[u]size[u]size[u]表示以uuu为根的子树大小。
公式解释：
- 如果没有限制，排列数为k!k!k!
- 对于每个节点uuu，其所有子孙在排列中必须保持uuu在它们前面的相对顺序
- 因此要除以每个节点的子树大小
扩展到森林（多棵树），公式变为：
ans=n!×∏i=1n1size[i](modM) ans = n! \times \prod_{i=1}^n \frac{1}{size[i]} \pmod{M}ans=n!×i=1∏nsize[i]1(modM)
算法步骤
- 预处理：计算111到400004000040000的阶乘模100000000710000000071000000007
- 建图：根据输入建立父子关系图
- 标记根节点：没有父亲的节点即为树的根
- 计算子树大小：从每个根节点开始执行DFS\texttt{DFS}DFS，计算每个节点的sizesizesize
- 计算结果：应用上述公式，使用模逆元处理除法
- 输出：对每个测试用例输出结果
参考代码
// Stand in a Line// UVa ID: 11174// Verdict: Accepted// Submission Date: 2025-11-01// UVa Run Time: 0.080s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMOD=1000000007;constintMAXN=40005;longlongfact[MAXN];vector<int>children[MAXN];intsz[MAXN];boolhasParent[MAXN];longlongmodPow(longlonga,longlongb){longlongres=1;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}returnres;}voiddfs(intu){sz[u]=1;for(intv:children[u]){dfs(v);sz[u]+=sz[v];}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);fact[0]=1;for(inti=1;i<MAXN;i++)fact[i]=fact[i-1]*i%MOD;intT;cin>>T;while(T--){intn,m;cin>>n>>m;for(inti=1;i<=n;i++){children[i].clear();hasParent[i]=false;}for(inti=0;i<m;i++){inta,b;cin>>a>>b;children[b].push_back(a);hasParent[a]=true;}for(inti=1;i<=n;i++)if(!hasParent[i])dfs(i);longlongr=fact[n];for(inti=1;i<=n;i++){r=r*modPow(sz[i],MOD-2)%MOD;}cout<<r<<"\n";}return0;}
