题目概述

我们知道，求任意图的最大独立集是一类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;
}