自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 21:49:42，当前版本为作者最后更新于2021-03-04 10:31:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种不用 2-SAT 的思路。

我们考虑选出的 后勤组织 的集合为 $A$ ，集合 $A$ 的大小为 $m$ 。

假设图中总边数为 $S$ ，那么 $A$ 中所有点的总 度数 $sum$ 应该等于 $S+\binom{m}{2}$。

显然，$sum \le S+ \binom{m}{2}$。所以在固定 $m$ 之后，我们只用判断度数最大的 $m$ 个点是否合法即可。

如果合法，可以考虑把度数最小的点换成其他度数相等的点，假设前 $m$ 个点选了 $a$ 个最小度数的点，总共有 $b$ 个最小度数的点，则贡献上 $\binom{b}{a}$ 即可。

可以做到 $O(n \log n )$ ，但因为读入都是 $O(n^2)$ 的，所以本文只实现了 $O(n^2)$。

（主要是我太懒了）

代码中取模是因为我感觉求个 $5000!$ 不取模太鬼畜了，可以证明答案是 $O(n)$ 的，所以取模也不会影响答案。

注意特判整个图是完全图的情况

//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register int
#define fr first
#define sd second
#define pa pair<int,int>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define N 5010
const int mod=998244353;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
inline int lowbit(int x){return x&(-x);}
int n,deg[N],x;
int S,fac[N],inv[N];
inline int C(int n,int m){return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int Z(int x){return (x>=mod?x-mod:x);}
int main()
{
	//ios::sync_with_stdio(false);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();FOR(i,1,n){deg[i]=read();int t=deg[i];while(t--){x=read();}S+=deg[i];}//没错这种做法边都不需要读入 
	S/=2;sort(deg+1,deg+n+1);reverse(deg+1,deg+n+1);
	fac[0]=1;
	FOR(i,1,n)fac[i]=1LL*fac[i-1]*i%mod;
	inv[0]=inv[1]=1;
	FOR(i,2,n)inv[i]=1LL*inv[mod%i]*(mod-mod/i)%mod;
	FOR(i,2,n)inv[i]=1LL*inv[i-1]*inv[i]%mod;
	int sum=0,ans=0;
	FOR(i,1,n)
	{
		sum+=deg[i];
		if(sum==S+i*(i-1)/2)
		{
			int a=0,b=0,pos=i;
			while(pos>=1&&deg[pos]==deg[i])a++,b++,pos--;
			pos=i+1;
			while(pos<=n&&deg[pos]==deg[i])b++,pos++;
			ans=Z(ans+C(b,a));
		}
	}
	if(deg[n]==n-1)ans=Z(ans+mod-1);//完全图 
	cout<<ans<<'\n';
	return 0;
}
//gl

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq