牛客小白月赛55 F 至至子的公司排队

牛客小白月赛55 F 至至子的公司排队

---

比较好理解的讲解： 官方视频讲解

---

思路： 此题解主要以个人学习为主，相对简略。说是比较经典的题目，与 树形 $dp$ 和 多重组合数 有关。多重排列的经典公式：
$$A=\frac{N！}{n1！n2！n3！...}$$

容易发现每一行都是一颗树，并且以拓扑序形式呈现。每将一颗子树当作根节点来看，其直接儿子结点构成了一组序列，例如其有 $3$ 个儿子结点，数量分别为 $2$ $3$ $4$ ，可视为 $aabbbcccc$ 的排列，若不考虑重复，那么方案数为 $9!$ ，若考虑重复我们还需要乘上 $2!3!4!$ 的逆元，简单可以理解为，原本 $4!$ 种不同选择固定为 $1$ 种，其余情况同，当然还要乘以每个结点自己的内在关系，即 $dp[son]$ 。多行的情况也是同样，考虑建立虚拟源点，所有 $boss$ 同一等级即可。

代码：

#include
using namespace std;
#define int long long 
#pragma GCC optimize(3)
#define re register int
typedef pair<int,int>PII;
#define pb push_back
#define mb pop_back
#define debug(a) cout<<a<<' ';
#define fer(i,a,b) for(re i=a;i<=b;i++)
#define der(i,a,b) for(re i=a;i>=b;i--)
const int N = 1e5+10;
const int mod = 1e9+7;
int ans=1;
int sum;
int dp[N];
int A[N];
int sz[N];
vector<int>v[N];
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void dfs(int u){
    bool ok = false;
    for(auto x:v[u]){
        ok = true;
        int j=x;
        dfs(j);
        sz[u]+=sz[j];
        dp[u]=dp[u]*qmi(A[sz[j]+1],mod-2)%mod*dp[j]%mod;
    }
    if(ok){
        dp[u]=dp[u]*A[sz[u]]%mod;
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    A[1]=1;
    for(int i=2;i<N;i++)A[i]=(A[i-1]*i)%mod;
    for(int i=0;i<n;i++){
        int m;
        cin>>m;
        for(int j=1;j<=m;j++)dp[j]=1,v[j].clear(),sz[j]=0;
        sum+=m;
        ans=ans*qmi(A[m],mod-2)%mod;
        for(int j=2;j<=m;j++){
            int x;
            cin>>x;
            v[x].pb(j);
            sz[x]++;
        }
        dfs(1);
        ans=ans*dp[1]%mod;
    }
    ans=ans*A[sum]%mod;
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66