menu ZigZagK的博客

正在努力加载中QAQ

[状压DP+组合]LOJ2540(PKUWC 2018)【随机算法】题解
apps LOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 164 次访问

题目概述

我们知道,求任意图的最大独立集是一类NP完全问题,目前还没有准确的多项式算法,但是有许多多项式复杂度的近似算法。

例如,小C常用的一种算法是:

  1. 对于一个 \(n\) 个点的无向图,先等概率随机一个 \(1..n\) 的排列 \(p[1..n]\)
  2. 维护答案集合 \(S\) ,一开始 \(S\) 为空集,之后按照 \(i=1..n\) 的顺序,检查 \(p[i]\cup S\) 是否是一个独立集,如果是的话就令 \(S=p[i]\cup S\)
  3. 最后得到一个独立集 \(S\) 作为答案。

小C现在想知道,对于给定的一张图,这个算法的正确率,输出答案对 \(998244353\) 取模。

解题报告

可以定义 \(f[i][s]\) 表示最大独立集大小为 \(i\) ,选的点状态为 \(s\) 的方案( \(0\) 没选 \(1\) 选了没用 \(2\) 用了),这样是 \(3\) 进制,不能承受。

然后我们发现一个点选了之后与其相连的点就不能选了,所以可以把这些点捆绑到该点上,这样就不用考虑选了没用的情况了,就变成了 \(2\) 进制了。具体可以Orz Lynstery

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=20,maxs=1<<maxn,MOD=998244353;

int n,m,fac[maxn+5],INV[maxn+5],S[maxn+5],si[maxs],f[maxn+5][maxs];
int E,lnk[maxn+5],nxt[maxn*maxn+5],son[maxn*maxn+5];

inline int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=(LL)s*w%MOD;b>>=1;if (b) w=(LL)w*w%MOD;}return s;}
inline void Make(int n){
    for (int i=fac[0]=INV[0]=1;i<=n;i++)
        fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=Pow(fac[i],MOD-2);
}
#define P(x,y) ((x)<(y)?0:(LL)fac[x]*INV[(x)-(y)]%MOD)
#define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);Make(n);
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    for (int i=1;i<=n;S[i]|=1<<i-1,i++)
        for (int j=lnk[i];j;j=nxt[j])
            S[i]|=1<<son[j]-1;
    for (int s=0;s<(1<<n);s++) for (int x=s;x;x-=x&-x) si[s]++;f[0][0]=1;
    for (int s=0;s<(1<<n);s++)
        for (int t=0;t<n;t++)
            if (f[t][s])
                for (int i=1;i<=n;i++)
                    if (!(s&(1<<i-1)))
                        AMOD(f[t+1][s|S[i]],(LL)f[t][s]*P(n-si[s]-1,si[S[i]-(s&S[i])]-1)%MOD);
    for (int i=n;i;i--)
        if (f[i][(1<<n)-1])
            return printf("%lld\n",(LL)f[i][(1<<n)-1]*INV[n]%MOD),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up