HUSTPC2022

H. Permutation Counting

Ideas ：
Yes $n(1\le n\le 2\cdot 10^6)$ A full permutation of numbers $a$, Known $n$ There is $m$ A constraint $x_i,y_i$, It is known that $a_{xi}<a_{yi}$, And $x_i$ Different from each other ,$y_i$ Could be the same
Ask how many possibilities there are to satisfy all constraints ？ Answer module $998244353$
Ideas ：
Establish a directed graph according to constraints , If there are rings in the graph , It is thought that there is no solution . conversely , Then there must be at least one understanding .
secondly , Because in the title $x_i$ Different from each other , We can see , If the $y_i\to x_i$ Even the edge , Will certainly form The forest
In order to turn the forest into a whole tree , Add extra points $n+1$, Connect to the roots of all trees , So we turn the forest into a whole tree
Tree form $dp$,$s{z}_i$ Said to $i$ Is the node size of the subtree of the tree root ,$f_i$ Express $s{z}_i$ Numbers in $i$ In the subtree of the root , How many permutations are there . that
consider $10$ Different stones are divided into $5,3,2$ Three piles
Yes $C_{10}^5\cdot C_5^3\cdot C_2^2$ Maybe
Then this question will be a size $10$ The tree of nodes is divided into $4,3,2$ The subtree of
Yes $C_9^4\cdot C_5^3\cdot C_2^2$ Maybe , The largest number must be the root node .
So you only need to satisfy the root node maximum , The remaining nodes can be divided arbitrarily

/* * @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]);
}