H. Permutation Counting

2022/7/28

传送门：https://codeforces.com/group/5zHJ4CTyoU/contest/392060/problem/H

图上计数，判环,拓扑。

题意：求n个数排列的方案数，满足m个限制条件：\(P_{x_i}<P_{y_i}\)，题目保证没有相同的y

解：

建成有向图图，是一个树林。

对于有环的图，答案为0。

对每颗树，树根用了他们的最大值，直接扔了不影响方案数，然后它的亲儿子们变成了新的树根，瓜分父亲遗产。假如树本有n个后代子节点，s个亲儿子，每个亲儿子分别有\(m_1,m_2...m_s\)个后代子节点。那么方案数有\(C_n^{m_1}*C_{n-m_1}^{m_2}...C_{m_s}^{m_s}\)

#include <bits/stdc++.h>
#define int long long
const int N = 4e6+10;
const int mo=998244353;
int a[N];
int fa[N];
int vis[N];
std::vector<int>to[N];
int ans=1;
int D[N],jc[N];
int q_pow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mo;
        a=a*a%mo;
        b>>=1;
    }
    return res;
}
int inv(int a){
    return q_pow(a,mo-2);
}
int C(int n,int m){
    int ans=jc[n];
    ans=ans*inv(jc[m])%mo;
    ans=ans*inv(jc[n-m])%mo;
    return ans;
}
void init(){
    D[2]=1;
    for(int i=3;i<N;i++)D[i]=(i-1)*(D[i-1]+D[i-2])%mo;
    D[0]=1;
    jc[0]=1;
    for(int i=1;i<N;i++)jc[i]=jc[i-1]*i%mo;

}
bool check=1;
int dfs(int now){
    vis[now]=1;
    if(to[now].size()==0)return 1;
    int sum=0;
    
    std::vector<int>ve;
    for(int i:to[now]){
        int k=dfs(i);
        ve.push_back(k);
        sum+=k;
    }
    int re=sum;
    for(int i:ve){
        ans*=C(sum,i);
        ans%=mo;
        sum-=i;
    }
    return re+1;
}
signed main(){
    std::ios::sync_with_stdio(false);
    init();
    int n,m;std::cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        std::cin>>x>>y;
        to[y].push_back(x);
        fa[x]=y;
    }
    for(int i=1;i<=n;i++)if(!fa[i])to[0].push_back(i);
    dfs(0);
    for(int i=1;i<=n;i++)if(!vis[i])ans=0;
    std::cout<<ans<<"\n";
}