题目描述

题解

之前做过一次

假设图建好了，设g[i]表示i->j（i<j）的个数

那么ans=∏(n-g[i])，因为连出去的必定会构成一个完全图，颜色互不相同

从n~1染色，点i的方案数是(n-g[i])

用线段树合并维护集合即可

code

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#define fo(a,b,c) for (a=b; a<=c; a++)

#define fd(a,b,c) for (a=b; a>=c; a--)

#define min(a,b) (a<b?a:b)

#define mod 998244353

using namespace std;

int tr[4000001][4];

int n,m,i,j,k,l,x,y,len;

long long ans,sum;

void swap(int &x,int &y)

{

	int z=x;

	x=y;

	y=z;

}

void New(int t,int x)

{

	if (!tr[t][x])

	{

		tr[t][x]=++len;

		tr[len][3]=n+1;

	}

}

void change(int t,int l,int r,int x)

{

	int mid=(l+r)/2;

	++tr[t][2];

	tr[t][3]=min(tr[t][3],x);

	if (l==r)

	return;

	if (x<=mid)

	{

		New(t,0);

		change(tr[t][0],l,mid,x);

	}

	else

	{

		New(t,1);

		change(tr[t][1],mid+1,r,x);

	}

}

int find(int t,int l,int r,int x,int y)

{

	int sum=0,mid=(l+r)/2;

	if (x<=l && r<=y)

	return tr[t][2];

	if (x<=mid)

	{

		if (tr[t][0])

		sum+=find(tr[t][0],l,mid,x,y);

	}

	if (mid<y)

	{

		if (tr[t][1])

		sum+=find(tr[t][1],mid+1,r,x,y);

	}

	return sum;

}

int Find(int t,int l,int r,int x)

{

	int mid=(l+r)/2,ans=n+1,s;

	if (x<=l) return tr[t][3];

	if (tr[t][0] && x<=mid)

	s=Find(tr[t][0],l,mid,x),ans=min(ans,s);

	if (tr[t][1])

	s=Find(tr[t][1],mid+1,r,x),ans=min(ans,s);

	return ans;

}

void merge(int t1,int t2,int l,int r)

{

	int mid=(l+r)/2;

	if (l==r) return;

	if (tr[t1][0] && tr[t2][0])

	merge(tr[t1][0],tr[t2][0],l,mid);

	else

	if (tr[t2][0])

	tr[t1][0]=tr[t2][0];

	if (tr[t1][1] && tr[t2][1])

	merge(tr[t1][1],tr[t2][1],mid+1,r);

	else

	if (tr[t2][1])

	tr[t1][1]=tr[t2][1];

	tr[t1][2]=tr[tr[t1][0]][2]+tr[tr[t1][1]][2];

	tr[t1][3]=min(tr[tr[t1][0]][3],tr[tr[t1][1]][3]);

}

int main()

{

	freopen("graph.in","r",stdin);

	freopen("graph.out","w",stdout);

	scanf("%d%d",&n,&m);

	len=n;

	fo(i,1,n)

	tr[i][3]=n+1;

	fo(i,1,m)

	{

		scanf("%d%d",&x,&y);

		if (x>y) swap(x,y);

		change(x,1,n,y);

	}

	tr[0][3]=n+1;

	ans=n;

	fo(i,1,n-1)

	{

		ans=(ans*(n-find(i,1,n,i+1,n)))%mod;

		j=Find(i,1,n,i+1);

		if (j<=n)

		merge(j,i,1,n);

	}

	printf("%lld\n",ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}