HUSTPC2022

H. Permutation Counting

思路：
有$n(1\le n\le 2\cdot 10^6)$个数字的全排列$a$，已知这$n$个数字间有$m$个约束$x_i,y_i$，已知$a_{xi}<a_{yi}$，且$x_i$互不相同，$y_i$可能相同
问有多少种满足所有约束的可能？对答案模$998244353$
思路：
根据约束建立有向图，若图中存在环，则认为无解。反之，则一定至少存在一种合理解。
其次，由于题目中$x_i$互不相同，我们可以得知，若将$y_i\to x_i$连边，则一定会形成森林
为了将森林变为一整颗树，加入额外点$n+1$，与所有树的树根连接，于是我们将森林变为了一整颗树
树形$dp$，$s{z}_i$表示以$i$为树根的子树节点大小，$f_i$表示$s{z}_i$个数字在以$i$为根的子树中，有多少种排列方法。那么
考虑将$10$个不同的石头分成$5,3,2$三堆
有$C_{10}^5\cdot C_5^3\cdot C_2^2$种可能
那么本题将一颗大小的$10$个节点的树分为$4,3,2$的子树
有$C_9^4\cdot C_5^3\cdot C_2^2$种可能，其中最大的数字一定是根节点。
所以只需要满足根节点最大，剩下的节点任意分即可

/* * @Author: zhangpangpang * @Date: 2022-06-09 09:29:49 * @Last Modified by: zhangpangpang * @Last Modified time: 2022-06-09 09:29:49 */
#include<bits/stdc++.h>
#define fi first
#define gcd __gcd
#define se second
#define pb push_back
#define lowbit(x) x&-x
#define inf 0x3f3f3f3f
#define mem(x,y) memset(x,y,sizeof(x))
#define lrb666 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<int,int> PII;
const int maxn=2e6+7;
int n,m,fa[maxn],d[maxn];
ll mod=998244353,sz[maxn],f[maxn],fac[maxn],inv[maxn],finv[maxn];
ll ksm(ll b,ll p){
    ll r=1;while(p>0){
    if(p&1){
    r=(r%mod*(b%mod))%mod;}p>>=1;b=(b%mod*(b%mod))%mod;}return r;}
void binom_init(int x) {
    
    fac[0] = fac[1] = 1;
    inv[1] = 1;
    finv[0] = finv[1] = 1;
    for(int i=2; i<x; i++){
    
        fac[i] = fac[i-1]*i%mod;
        inv[i] = mod-mod/i*inv[mod%i]%mod;
        finv[i] = finv[i-1]*inv[i]%mod;
    }
}
ll binom(ll n, ll r){
    
    if(n<r || n<0 || r<0) return 0;
    return fac[n]*finv[r]%mod*finv[n-r]%mod;
}
int find(int x)
{
    
	if(x==fa[x])
	return fa[x];
	else
	return fa[x]=find(fa[x]);
}
void lianjie(int x,int y)
{
    
	int px=find(x),py=find(y);
	fa[px]=py;
}
vector<int>v[maxn];
void dfs(int u,int fa)
{
    
	sz[u]=1;f[u]=1;
	ll use=0;
	for(auto nx:v[u])
	{
    
		if(u==fa) continue;
		dfs(nx,u);
		sz[u]+=sz[nx];
	}
	use++;
	for(auto nx:v[u])
	{
    
		if(u==fa) continue;
		f[u]=(f[u]*f[nx])%mod;
		f[u]=(f[u]*binom(sz[u]-use,sz[nx]))%mod;
		use+=sz[nx];
	}
}
int main()
{
    
	binom_init(maxn-5);
	scanf("%d%d",&n,&m);int ok=1;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
    
		int a,b;scanf("%d%d",&a,&b);
		d[a]++;
		v[b].pb(a);
		if(find(a)==find(b)) ok=0;
		else lianjie(a,b);
	}
	for(int i=1;i<=n;i++)
	{
    
		if(d[i]==0) v[n+1].pb(i);
	}
	if(!ok)
	{
    
		puts("0");return 0;
	}
	dfs(n+1,-1);
	printf("%lld\n",f[n+1]);
}