P3513 [POI2011]KON-Conspiracy

· · 题解

提供一种不用 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