题解 P5492 [PKUWC2018]随机算法

· · 题解

Solution

我们可以先求出所有的最大独立集 , 这个直接枚举所有子集之后进行判定即可 .
一个图的最大独立集个数为一般不会太大 , 且本题中 n\leq 20 , 所以个数很小 , 本题数据中最多的个数只达到了 76 个 , 那么我们考虑枚举所有最大独立集 .
设 f_j表示集合 j 中所有的元素进行排列 , 按照题目的算法得出的集合是当前枚举的最大独立集的子集的方案数 .
设当前枚举的最大独立集为 i ,
那么有转移 f_{j\cup k}+=f_j , 当

求出的 f_{all} 即为求出集合为当前枚举的最大独立集的序列数 , 其中 all 为全集 ,
答案即为所有 f_{all} 的和
对于每一个最大独立集枚举全部状态和转移为 O(n*2^n) , 总时间复杂度为 O(n2^n*玄学) , 不过也跑不满 .
卡最大独立集数量的 hack 数据

20 10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define il inline
#define reg register
using namespace std;
il int read()
{
    reg int ret=0;reg char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return ret;
}
const int maxn=20;
const int maxm=200;
const int mod=998244353;
int n,m;
il int qpow(reg int a,reg int b)
{
    reg int ret=1;
    for(;b;b>>=1)
    {
        if(b&1)ret=(ll)ret*a%mod;
        a=(ll)a*a%mod;
    }
    return ret;
}
il int qmod(reg int a){return a>=mod?a-mod:a;}
int ord[1<<maxn];
int to[maxn];
il void link(reg int x,reg int y){to[x]|=(1<<y);to[y]|=(1<<x);}//记录一个点的可达点集合
il bool judge(reg int x)//判断是否为独立集
{
    while(x)
    {
        reg int now=x&(-x);
        x-=now;
        now=ord[now];
        if(x&to[now])return false;
    }
    return true;
}
il bool judge(reg int x,reg int p)//判断点x和集合p的并集是否为独立集
{
    if(to[x]&p)return false;
    return true;
}
int all;
bool ind[1<<maxn];int cnt[1<<maxn];int mx;
int f[1<<maxn],ans;
int main()
{
    n=read();m=read();all=(1<<n)-1;
    for(int i=0;i<n;i++)ord[1<<i]=i;
    for(reg int i=1;i<=m;i++)link(read()-1,read()-1);
    for(reg int i=0;i<=all;i++)cnt[i]=cnt[i>>1]+(i&1);
    for(reg int i=all;i>=0;i--)//求出所有最大独立集
    {
        if(cnt[i]<mx)continue;
        if(judge(i))mx=cnt[i],ind[i]=1;
    }
    for(reg int i=0;i<=all;i++)
    {
        if(cnt[i]<mx||!ind[i])continue;
        for(reg int j=0;j<=all;j++)f[j]=0;
        f[0]=1;
        for(reg int j=0;j<=all;j++)
        {
            if(!f[j])continue;
            reg int np=j&i;
            for(reg int k=0;k<n;k++)
            {
                if((j>>k)&1)continue;
                if(((i>>k)&1)||!judge(k,np))f[j|(1<<k)]=qmod(f[j|(1<<k)]+f[j]);
            }
        }
        ans=qmod(ans+f[all]);
    }
    for(reg int i=2;i<=n;i++)ans=(ll)ans*qpow(i,mod-2)%mod;
    printf("%d",ans);
    return 0;
}