[PKUWC2018]随机算法

· · 题解

给你一张无向图。使用如下算法生成一个独立集：

  • 随机生成一个排列 p。令 S=\varnothing。
  • 按 i=1...n 的顺序，若 \{p_i\}\cup S 是一个独立集，则使 S=\{p_i\}\cup S。

求最终 S 为图的最大独立集的概率。

分享一个普及水平的做法。

先使用状压 DP 求出图的所有最大独立集。对于每个最大独立集，暴力 DP 求可行排列数。

事实上，根据 这篇论文，阶为 20 的图的最大独立集个数至多有 1020 个，所以这种做法的时间频度是可以被卡成数十亿的。不过一般的图远远无法卡到上限，比如该题的最大测试点仅有 18 个最大独立集。

#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;
const int MOD = 998244353;

int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = (ll)res * a % MOD;
        a = (ll)a * a % MOD, b >>= 1;
    }
    return res;
}

int n, m, vist, G[20], pop[1 << 20], tot, ans, fact = 1, f[1 << 20] = {1}, lg[1 << 20] = {-1};
std::vector<bool> dp;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int u, v;
        scanf("%d%d", &u, &v), --u, --v;
        G[u] |= 1 << v, G[v] |= 1 << u;
    }
    dp.resize(1 << n), dp[0] = 1;
    for(int i = 1; i < (1 << n); ++i){
        pop[i] = pop[i >> 1] + (i & 1), lg[i] = lg[i >> 1] + 1;
        for(int j = 0; j < n; ++j)
            if(!(G[j] & i) && (i & (1 << j) && dp[i ^ (1 << j)])){
                dp[i] = 1, tot = std::max(tot, pop[i]);
                break;
            }
    }
    for(int S = 0; S < (1 << n); ++S)
        if(pop[S] == tot && dp[S]){
            for(int i = 1; i < (1 << n); ++i){
                f[i] = 0;
                for(int x = i; x; x -= x & -x){
                    static int j; j = lg[x & -x];
                    if(!(S & (1 << j)) && !(i & G[j] & S))
                        continue;
                    f[i] = (f[i] + f[i ^ (1 << j)]) % MOD;
                }
            }
            ans = (ans + f[(1 << n) - 1]) % MOD;
        }
    for(int i = 1; i <= n; ++i) fact = (ll)fact * i % MOD;
    ans = (ll)ans * qpow(fact, MOD - 2) % MOD;
    printf("%d\n", ans);
    return 0;
}