【pkuwc2018】随机算法

我们考虑用状压dp来解决这一道题

设$f[i][S]$表示当前排列的前i位所构成的最大独立集恰好为S的方案数

我们考虑用$f[i][S]$推出$f[i+1][S']$的值

那么我们有两种扩展的方法，一种是在第$i+1$位，加入一个数$j$，满足$S∩j=∅$，且$S∪j$为最大独立集。

这种情况，相当于在原本的最大独立集中，新加入了一个点j，那么显然可以对答案产生贡献

则有$f[i+1][S|(1<<j)]+=f[i][S]$

另一种是：我们在第i+1位，填入一个不会对最大独立集产生变化的数。

根据题意，我们要填入一个数j，满足集合S中，存在于节点$j$相邻的点。

则有$f[i+1][S]+=f[i][S]*(p[S]-i) $，其中$p[S]$表示与集合$S$相连的点的个数+集合$S$所包含的点数

设题目中所给的图的最大独立集大小为$k$

最后的答案显然为$\dfrac{\sum\limits_{|S|=k}f[n][k]}{n!}$

#include<bits/stdc++.h>

#define M 20

#define lowbit(x) ((x)&(-(x)))

#define MOD 998244353

#define L long long

using namespace std;

L pow_mod(L x,L k){L ans=1; for(;k;k>>=1,x=x*x%MOD) if(k&1) ans=ans*x%MOD; return ans;}

int a[M],ok[1<<M],p[1<<M],siz[1<<M];

L f[M+1][1<<M];

int n,m,U;

int main(){

    scanf("%d%d",&n,&m);

    U=1<<n;

    for(int i=1;i<U;i++) siz[i]=siz[i-lowbit(i)]+1;

    for(int i=0;i<n;i++) a[i]^=(1<<i);

    for(int i=1;i<=m;i++){

        int x,y; scanf("%d%d",&x,&y);

        x--; y--;

        a[x]^=(1<<y); a[y]^=(1<<x);

    }

    ok[0]=1;

    for(int i=0;i<U;i++)

    if(ok[i]){

        for(int j=0;j<n;j++)

        if((i&a[j])==0)

        ok[i|(1<<j)]=1;

    }

    int maxn=0;//最大独立集大小

    for(int i=1;i<U;i++) if(ok[i]) maxn=max(maxn,siz[i]);

    for(int i=1;i<U;i++)

    for(int j=0;j<n;j++)

    if(i&a[j]) p[i]++;

    //p[S] 与点集S相连的点数为多少（包括S中的点）

    f[0][0]=1;

    for(int i=0;i<n;i++)

    for(int S=0;S<U;S++)

    if(f[i][S]){

        f[i+1][S]=(f[i+1][S]+f[i][S]*(p[S]-i))%MOD;

        for(int j=0;j<n;j++)

        if((S&(1<<j))==0&&ok[S|(1<<j)]){

            f[i+1][S+(1<<j)]=(f[i+1][S+(1<<j)]+f[i][S])%MOD;

        }

    }

    L ans=0;

    for(int S=1;S<U;S++)

    if(siz[S]==maxn&&ok[S]==1)

    ans=(ans+f[n][S])%MOD;

    L fac=1;

    for(int i=1;i<=n;i++) fac=fac*i%MOD;

    printf("%lld\n",ans*pow_mod(fac,MOD-2)%MOD);

}

巴特西

【pkuwc2018】随机算法

最新文章

热门文章