LOJ2540「PKUWC2018」随机算法

又是一道被咕了很久的题 貌似从WC2019之前咕到了现在

我们用f[i][s]表示现在最大独立集的大小为i 不可选集合为s

然后转移O(n)枚举加进来的点就比较简单啦

这个的复杂度是O(2^n*n^2)

据说有更科学的O(2^n*n)

但是显然这个做法就能过了（

详情参见PKUWC2019D1T1（大雾

代码扔这里了。

//Love and Freedom.

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdio>

#define ll long long

#define inf 20021225

#define mdn 998244353

#define N 21

using namespace std;

int read()

{

    int s=,f=; char ch=getchar();

    while(ch<'' || ch>'')    {if(ch=='-') f=-;ch=getchar();}

    while(ch>='' && ch<='')    s=s*+ch-'',ch=getchar();

    return f*s;

}

int ksm(int bs,int mi)

{

    int ans=;

    while(mi)

    {

        if(mi&)    ans=1ll*ans*bs%mdn;

        bs=1ll*bs*bs%mdn; mi>>=;

    }

    return ans;

}

int f[N][<<N],fac[N],inv[N],cnt[<<N],n,w[N];

void add(int x,int y)

{

    w[x]|=<<y; w[y]|=<<x;

}

int A(int n,int m)

{

    if(n<m)    return ;

    return 1ll*fac[n]*inv[n-m]%mdn;

}

void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;}

int main()

{

    n=read(); int m=read(); fac[]=; int x,y;

    for(int i=;i<=n;i++)    fac[i]=1ll*fac[i-]*i%mdn;

    inv[n]=ksm(fac[n],mdn-);

    for(int i=n;i;i--)    inv[i-]=1ll*inv[i]*i%mdn;

    for(int i=;i<=m;i++)    x=read(),y=read(),add(x-,y-);

    for(int i=;i<n;i++)    w[i]|=<<i;

    f[][]=; int top=<<n;

    for(int i=;i<top;i++)    cnt[i]=cnt[i>>]+(i&);

    for(int i=;i<n;i++)    for(int s=;s<top;s++)

        if(f[i][s])    for(int j=;j<n;j++) if(!((s>>j)&))

            upd(f[i+][s|w[j]],1ll*f[i][s]*A(n-cnt[s]-,cnt[w[j]-(w[j]&s)]-)%mdn);

    for(int i=n;i;i--)    if(f[i][top-])

    {

        printf("%d\n",1ll*f[i][top-]*inv[n]%mdn);

        break;

    }

    return ;

}