[LOJ#2540][PKUWC2018]随机算法(概率DP)

场上数据很水，比较暴力的做法都可以过90分以上，下面说几个做法。

1. 暴力枚举所有最大独立集，对每个独立集分别DP。复杂度玄学，但是由于最大独立集并不多，所以可以拿90.

2. dp[S][k]表示考虑到排列的第k位，当前独立集为S的方案数，枚举第k+1位，根据是否与S相连转移到dp[S][k+1]或dp[S | a[k+1]][k+1]。$O(n^22^n)$

3. dp[S]表示排列的状态为S时的正确率，mx[S]表示排列状态为S时能得到的最大独立集大小，考虑转移，枚举排列里最后一个在独立集中的点i∈S，从S中删去所有与i相连的点得到S'，若mx[S]<mx[S']+1则更新mx[S]，dp[S]清零，否则累加。注意到每个排列都是等概率出现的，所以最后直接除以|S|即可。 $O(n2^n)$

方法一：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define ll long long
using namespace std;

const int N=1<<22,mod=998244353;
ll n,m,x,y,s[25],p[25],f[N][25],cnt,mx,v[N],num[N],t[N],ans,o[N];

int main(){
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    p[1]=1; rep(i,2,n) p[i]=p[i-1]<<1;
    rep(i,1,m) scanf("%lld%lld",&x,&y),s[x]|=p[y],s[y]|=p[x];
    cnt=(1<<n)-1; f[0][0]=1;
    rep(i,0,cnt){
        ll tmp=0; v[i]=1;
        rep(j,1,n) if ((i&p[j])&&(s[j]&i)) v[i]=0;
        if (v[i]){
            rep(j,1,n) if (i&p[j]) tmp++,t[i]|=s[j];
            num[i]=tmp; mx=max(mx,tmp);
            tmp=0;
            rep(j,1,n) if (t[i]&p[j]) tmp++;
            o[i]=tmp;
        }
    }
    rep(i,0,cnt) if (v[i])
        rep(j,0,o[i]){
            if (j!=o[i]) f[i][j+1]=(f[i][j+1]+f[i][j]*(o[i]-j))%mod;
            rep(k,1,n) if (!(i&p[k])&&!(p[k]&t[i])) f[i|p[k]][j]=(f[i|p[k]][j]+f[i][j])%mod;
            if (num[i]==mx && j==o[i]) ans=(ans+f[i][j])%mod;
        }
      printf("%lldn",ans);
      return 0;
}

方法二：

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define P 998244353
#define N 21
#define t (1<<n)
int n,m;
long long ans=0;
bool flag[1<<(N-1)];
int s[1<<(N-1)],w[N],v[1<<(N-1)],cnt[1<<(N-1)],tot[1<<(N-1)],f[21][1<<(N-1)],maximum=1;
int main()
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=n;i++) w[i]=1<<(i-1),s[w[i]]=w[i];
    for (int i=1;i<=m;i++) 
    {
        int x=read(),y=read();
        s[w[x]]|=w[y],s[w[y]]|=w[x];
    }
    flag[0]=1;
    for (int i=0;i<t;i++)
    if (flag[i])
        for (int j=1;j<=n;j++)
        if (!(w[j]&s[i])) 
        {
            flag[i|w[j]]=1,s[i|w[j]]=s[i]|s[w[j]],cnt[i|w[j]]=cnt[i]+1;
            if (cnt[i]>=maximum) maximum=cnt[i|w[j]];
        }
    for (int i=0;i<t;i++) 
    {
        s[i]=(~s[i])&(t-1);
        register int k=s[i];
        while (k) k^=k&-k,tot[i]++;
        v[i]=i&-i;
    }
    f[0][0]=1;
    for (register int i=0;i<n;i++)
        for (register int j=0;j<t;j++)
        if (f[i][j]) 
        {
            for (register int k=s[j];k;k^=v[k])
            f[i+1][j|v[k]]=(f[i+1][j|v[k]]+f[i][j])%P;
            f[i+1][j]=(1ll*f[i][j]*(n-i-tot[j])+f[i+1][j])%P;
        }
    for (int i=0;i<t;i++) if (cnt[i]==maximum) ans=(ans+f[n][i])%P;
    cout<<ans;
    fclose(stdin);fclose(stdout);
    return 0;
}

方法三：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std;

const int N=21,mod=998244353;
int n,m,x,y,inv[N],f[N],mx[1<<N],F[1<<N];

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,m) scanf("%d%d",&x,&y),x--,y--,f[x]|=1<<y,f[y]|=1<<x;
    inv[1]=1; f[0]|=1; F[0]=1;
    rep(i,2,n) f[i-1]|=(1<<(i-1)),inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    for (int i=1; i<(1<<n); i++){
        int tot=0;
        for (int j=0; j<n; j++) if (i&(1<<j)){
            int s=i&(~f[j]);
            if (mx[i]<mx[s]+1) mx[i]=mx[s]+1,F[i]=0;
            if (mx[i]==mx[s]+1) F[i]=(F[i]+F[s])%mod;
            tot++;
        }
        F[i]=1ll*F[i]*inv[tot]%mod;
    }
    printf("%dn",F[(1<<n)-1]);
    return 0;
}