问题描述

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

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

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

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

输入

第一行两个非负整数 $n,m$ 表示给定的图的点数和边数。

接下来 $m$ 行,每行有两个正整数 $(u,v) (u\neq v)$ 描述这张图的一条无向边。

输出

输出正确率,答案对 $998244353$ 取模。

思路

这题比较巧妙的地方就是设计状态。考虑比较朴素的一种方法, $0$ 表示一个点未被选,$1$ 表示一个点选了但没在集合中,$2$ 表示一个点在集合中,这样的状态数就是 $n^3$,我们需要考虑的就是如何优化这种状态。

这里要跳出按照排列的顺序选点这个思维定式。只要选了点 $i$ 加入独立集中,那么与 $i$ 相邻的点在它之后任意时候选都不会产生影响,所以假设有 $s1$ 个点没有考虑,这其中有 $s2$ 个点是与 $i$ 相邻的,那么我们考虑这 $s2$ 个点在排列中的情况数,不难发现这个就是 $A_{s1}^{s2}$。注意我们这里说的是「考虑」而不是选取,也就是说先预先给 $s2$ 个点排好位置,而不是按照排列的顺序依次选了这些点。

所以我们可以这样设计状态,设 $f_{S, i}$ 为考虑了集合 $S$ 且其中独立集大小为 $i$ 的方案数。按照上文提到的考虑方法,可以知道只要是不属于集合 $S$ 的点一定可以加入 $S$ 中的独立集,因为与独立集相邻的点已经在 $S$ 中了。设已经考虑了点集 $S$ ,此时要加入点 $k$,与$k$ 相邻的点集为 $e_k$,还有 $s1$ 个点没有考虑,这其中有 $s2$ 个点是与 $k$ 相邻的,有转移方程

$$f_{S \bigcup e_k, i+1} +=f_{S, i} * A_{s1}^{s2}$$

其中 $k\notin S$,$s1=n-|S|-1$,$s2=|e_k\bigcap(e_k\bigcup S)|$。这样转移总复杂度就是 $O(n^22^n)$ 了。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 25
#define MAXM (1<<20)+5
#define INF 0x3f3f3f3f
#define p 998244353
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, e[MAXN], f[MAXM][MAXN], bit[MAXM], fac[MAXN], inv[MAXN];

void init()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(rint i=0; i<(1<<n); ++i) bit[i]=bit[i>>1]+(i&1);
    for(rint i=2; i<=n; ++i) inv[i]=1LL*inv[p%i]*(p-p/i)%p;
    for(rint i=2; i<=n; ++i)
    {
        inv[i]=1LL*inv[i]*inv[i-1]%p;
        fac[i]=1LL*fac[i-1]*i%p;
    }
}

int A(int x, int y)
{
    return 1LL*fac[x]*inv[x-y]%p;
}

int main()
{
    scanf("%d%d", &n, &m);
    init();
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        x--, y--;
        e[x]|=(1<<y);
        e[y]|=(1<<x);
    }
    for(rint i=0; i<n; ++i) e[i]|=(1<<i);
    f[0][0]=1;
    for(rint sta=0; sta<(1<<n); ++sta)
        for(rint i=0; i<n; ++i)
        {
            if(!f[sta][i]) continue;
            for(rint j=0; j<n; ++j)
                if(!((sta>>j)&1))
                {
                    int nxt=sta|e[j], s1=n-bit[sta]-1, s2=bit[e[j]^(e[j]&sta)]-1;
                    f[nxt][i+1]=(f[nxt][i+1]+1LL*f[sta][i]*A(s1, s2)%p)%p;
                }
        }
    for(rint i=n; i>=0; i--)
        if(f[(1<<n)-1][i])
        {
            printf("%lld\n", 1LL*f[(1<<n)-1][i]*inv[n]%p);
            return 0;
        }
    return 0;
}

1 对 “LOJ2540 随机算法 [计数类DP]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注