题意

有一种贪心求最大独立集的算法：

1. 随机一个排列
2. 按顺序加入独立集，如果一个点能加入，就加入\({S}\)

给出一张图，问得出正确答案的概率。

\(n \leq 20\)

传送门

思路

用 \(dp[i][s]\) 表示排列集合为 \(i\)，最大独立集的大小为 \(s\) 的方案数，\(a[x]\)表示与\(x\)相连的点集。

考虑加入一个可行点，会使与它相连的所有点不能再加入，这些点的排列顺序无关答案，可以直接将他们随便放到后面的排列中去，即乘上\(A(n-count[i]-1,count[a[j]]-count[i \& a[j]]-1)\)，将这些点看作已经在排列里了，继续转移

因为对于一个排列集合，我们只需要转移\(s\)最大的即可（小的不可能成为答案），所以复杂度是\(O(n \times 2^n)\)的

#include <bits/stdc++.h>
const int mu=998244353;
int p[25],inv[25],dp[1<<20][21],a[20],n,m,count[1<<20],x,y;
int ksm(int x,int y){
    int ans=1;
    for (;y;y>>=1,x=x*1ll*x%mu)
        if (y&1) ans=ans*1ll*x%mu;
    return ans;
}
int A(int x,int y){
    return 1ll*p[x]*inv[x-y]%mu;
} 
void init(){
    p[0]=1;
    for (int i=1;i<=20;i++) p[i]=p[i-1]*1ll*i%mu;
    inv[20]=ksm(p[20],mu-2);
    for (int i=20;i>=0;i--) inv[i-1]=inv[i]*1ll*i%mu; 
    for (int i=1;i<1<<n;i++)
        count[i]=count[i>>1]+(i&1);
} 
int main(){
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) a[i]|=(1<<i);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        x--,y--;
        a[x]|=(1<<y),a[y]|=(1<<x);
    }
    init();
    dp[0][0]=1;
    for (int i=0;i<(1<<n)-1;i++)
        for (int k=count[i];k>=0;k--){
            int t=dp[i][k];
            if (!t) continue;
            for (int j=0;j<n;j++){
                if (i&(1<<j)) continue;
                int u=i|a[j];
                dp[u][k+1]=(dp[u][k+1]+t*1ll*A(n-count[i]-1,count[a[j]]-count[i&a[j]]-1))%mu;
            }   
            break;
        }   
    for (int i=n;i>=1;i--)
        if (dp[(1<<n)-1][i]){ 
            printf("%d\n",dp[(1<<n)-1][i]*1ll*inv[n]%mu);
            return 0;
        }
} 

后记

为什么我有点迷糊pku的难度？？今年sc是迷惑行为吗？？