「PKUWC2018」随机算法 题解

问题描述

给定一张无向图，求随机排列算法得到最大独立集的概率，结果对 $998244353$ 取模。
随机排列算法的步骤：

1. 随机生成一个节点排列 $p[1..n]$。
2. 按顺序检查每个节点 $p[i]$，若将其加入当前集合 $S$ 后仍为独立集，则加入 $S$。
3. 最终 $S$ 为算法输出，求 $S$ 是最大独立集的概率。

核心思路

1. 最大独立集大小求解：先确定图的最大独立集的大小 $k$。
2. 概率计算：通过动态规划（DP）模拟算法执行过程，计算算法输出独立集大小为 $k$ 的概率。

详细分析

1. 最大独立集大小求解

最大独立集是指图中最大的顶点子集，其中任意两顶点不相邻。

• 用二进制掩码表示顶点子集：掩码 $i$ 的第 $j$ 位为 $1$ 表示包含顶点 $j$。
• 标记非独立集：若掩码 $i$ 包含相邻顶点，则 $i$ 不是独立集（记为 $g[i] = 1$）。
• 递推标记：若掩码 $j$ 是非独立集，则包含 $j$ 的所有掩码均为非独立集。
• 最大独立集大小：在所有 $g[i] = 0$（即独立集）的掩码中，取顶点数最多的大小。

2. 概率计算（动态规划）

算法的核心是模拟随机排列中节点的选择过程，追踪每个状态的概率。

• 状态表示：用 $3$ 进制数表示每个节点的状态：

  • $0$：未处理（尚未考虑该节点）。
  • $1$：已加入独立集 $S$。
  • $2$：被排除（因相邻节点已加入 $S$）。
    例如，$3$ 进制数 120 表示：节点 $1$ 加入 $S$，节点 $2$ 被排除，节点 $3$ 未处理。

• 状态生成：通过 DFS 生成所有合法状态。合法状态需满足：若节点 $u$ 加入 $S$（状态 $1$），则其所有邻居必须被排除（状态 $2$）。

• DP 定义：$f[i]$ 表示到达第 $i$ 个状态的概率。初始状态为 $0$（所有节点未处理），概率为 $1$。

• 状态转移：对于每个状态 $S$，从所有未处理节点（状态 $0$）中随机选择一个节点 $u$：

  • 若 $u$ 可加入 $S$（其邻居均未加入 $S$），则生成新状态 $T$（$u$ 设为 $1$，其邻居设为 $2$）。
  • 转移概率为 $\frac{1}{k}$（$k$ 为当前未处理节点数），用乘法逆元在模意义下计算。

• 结果计算：累加所有最终状态（无未处理节点）中，独立集大小等于最大独立集大小的概率之和。

代码解析

1. 输入与预处理：
   读入图的边，用邻接矩阵 $a$ 存储。预处理 $3$ 的幂次 $pw3$，用于状态的 $3$ 进制表示。

2. 状态生成：
   用 DFS 从初始状态 $0$ 出发，递归生成所有合法状态，存入 states 并去重。

3. DP 初始化与转移：

   • cnt[i] 记录状态 states[i] 中未处理节点的数量。
   • 对每个状态，计算其可转移到的新状态，更新 DP 数组 $f$。

4. 最大独立集计算：
   用二进制掩码和递推标记非独立集，找到最大独立集大小。

5. 结果累加：
   遍历所有状态，累加独立集大小等于最大的状态的概率，输出结果。

复杂度分析

• 状态数：$3^n$ 是理论上限，但实际合法状态远小于此（因约束条件），对于 $n=20$ 可接受。
• 时间复杂度：主要取决于状态数 $k$，转移过程为 $O(k \cdot n)$，整体可通过 $n=20$ 的数据。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 21, Mod = 998244353;
int n, m, k;
int a[N][N], pw3[N], g[1 << N];
unordered_set<int> h;
vector<int> states, f, cnt;

int qmi(int a, int b = Mod - 2) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

void dfs(int S) {
    if (h.count(S)) return;
    h.insert(S);
    states.push_back(S);
    for (int i = 1; i <= n; ++i) {
        int T = S;
        if (S / pw3[i - 1] % 3) continue;
        S += pw3[i - 1]; // 标记i为已加入(1)
        bool valid = true;
        for (int j = 1; j <= n; ++j) {
            if (a[i][j]) {
                if (S / pw3[j - 1] % 3 == 1) { // 邻居已加入，不合法
                    valid = false;
                    break;
                }
                if (S / pw3[j - 1] % 3 != 2) // 标记邻居为排除(2)
                    S += 2 * pw3[j - 1];
            }
        }
        if (valid) dfs(S);
        S = T;
    }
}

void calc(int S, vector<int>& p) {
    p.clear();
    for (int i = 1; i <= n; ++i) {
        int T = S;
        if (S / pw3[i - 1] % 3) continue;
        S += pw3[i - 1];
        bool valid = true;
        for (int j = 1; j <= n; ++j) {
            if (a[i][j]) {
                if (S / pw3[j - 1] % 3 == 1) {
                    valid = false;
                    break;
                }
                if (S / pw3[j - 1] % 3 != 2)
                    S += 2 * pw3[j - 1];
            }
        }
        if (valid && h.count(S)) p.push_back(S);
        S = T;
    }
}

signed main() {
    n = read(), m = read();
    while (m--) {
        int x = read(), y = read();
        a[x][y] = a[y][x] = 1;
    }
    pw3[0] = 1;
    for (int i = 1; i <= 20; ++i) pw3[i] = pw3[i - 1] * 3;
    dfs(0);
    sort(states.begin(), states.end());
    k = states.size();
    f.resize(k), cnt.resize(k);
    for (int i = 0; i < k; ++i) {
        int s = states[i];
        cnt[i] = 0;
        for (int j = 0; j < n; ++j)
            if ((s / pw3[j]) % 3 == 0) cnt[i]++;
    }
    f[0] = 1;
    vector<int> p;
    for (int i = 0; i < k; ++i) {
        calc(states[i], p);
        for (int T : p) {
            int j = lower_bound(states.begin(), states.end(), T) - states.begin();
            f[j] = (f[j] + f[i] * qmi(cnt[i])) % Mod;
        }
    }
    // 计算最大独立集大小
    memset(g, 0, sizeof g);
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i][j])
                g[(1 << (i - 1)) | (1 << (j - 1))] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < (1 << n); ++j)
            if (!(j & (1 << (i - 1))))
                g[j | (1 << (i - 1))] |= g[j];
    int max_sz = 0;
    for (int i = 0; i < (1 << n); ++i)
        if (!g[i])
            max_sz = max(max_sz, (int)__builtin_popcount(i));
    // 累加答案
    int ans = 0;
    for (int i = 0; i < k; ++i) {
        int s = states[i];
        int sz = 0;
        for (int j = 0; j < n; ++j)
            if ((s / pw3[j]) % 3 == 1) sz++;
        if (sz == max_sz) ans = (ans + f[i]) % Mod;
    }
    printf("%lld\n", ans);
    return 0;
}

总结

本题通过状态压缩（3进制表示）和动态规划模拟随机算法的执行过程，结合独立集的特性高效计算概率。核心在于准确建模状态转移和利用模运算处理概率计算，最终成功求解最大独立集的正确率。