题解-PKUWC2018 随机算法

Problem

loj2540

题意简述：给定(n)个点的无向图，给定求最大独立集的近似算法：随机排列(1cdots n)，按照该排列顺序贪心构造最大独立集（即对每个点能加入独立集就加），求算法正确率

(nleq 20,mleq binom n2)

Solution

暴力枚举应有(10pts)（(nleq 9))

当前状态集合为(S)，(0,1,2)分别表示没访问到、访问到且在最大独立集内、访问到且未在最大独立集内，每次枚举下一个访问的节点，复杂度(O(n3^n))，应有(30pts)（(nleq 13)）

然而我并没有想到(70pts)（(nleq 17)）的做法，可能是(O(n^22^n))？

一种玄学暴力，枚举所有最大独立集，然后(f[S])来dp转移，最坏复杂度(O(2^ncdot 2^nn))，但由于一个图的最大独立集没有多少，所以应该能拿一个很高的分（据学长说这个算法好像可以(100pts)）

算了，还是来想点正经的，预估复杂度为(O(n2^n))，所以大致是设答案为(f[S])，然后枚举点进行转移

接着(30pts)做法，要将状态数降至(2^n)，需要将三种状态中合并两种……然而到这我就不会了qwq

把范围展开一点，(f[S])表最大独立集与与其相连的节点集合（独立集辐射范围）为(S)时的最大独立集大小，用(g[S])计数，最终(g[U])即为答案

转移就相当于每次在(S)里刨掉某个点与与其相连的点，好像就没了？（由于算的是期望且每个状态的步数不同，处理完每个(g(T))后要将(g(T))除以(|T|)）

upd：看了题解后发现好像(70pts)就是我的做法再加个状态表示(S)的最大独立集大小（而且更显而易见），但由于每个(S)的最大独立集大小唯一，所以不需要这么设置

看了题解后发现有个方程更容易想，设(S)为独立集辐射范围（就是上面的定义），设(w)为当前枚举点的控制范围：

[f(Scup w)+=f(S)cdot P_{n-|S|-1}^{|w|-|wcap S|-1}]

Code

#include <cstdio>

const int N=21,M=1<<N,p=998244353;
int d[N],bin[N],inv[N],f[M],g[M];
int n,m,lim;

inline int pls(int&x,int y){x=x+y<p?x+y:x+y-p;}

int main(){
    scanf("%d%d",&n,&m);lim=1<<n;
    d[1]=bin[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=n;++i){
        d[i]=bin[i]=bin[i-1]<<1;
        inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    }
    for(int i=m,x,y;i;--i){
        scanf("%d%d",&x,&y);
        d[x]|=bin[y];
        d[y]|=bin[x];
    }
    
    g[0]=1;
    for(int S=1,tt,s;S<lim;++S){
        tt=0;
        for(int i=1;i<=n;++i)
            if(S&bin[i]){
                ++tt,s=S&(~d[i]);
                if(f[S]<f[s]+1)f[S]=f[s]+1,g[S]=0;
                if(f[S]==f[s]+1)pls(g[S],g[s]);
            }
        g[S]=1ll*g[S]*inv[tt]%p;
    }
    printf("%dn",g[lim-1]);
    return 0;
}