RenaMoe's Blog

念念不忘，必有回响

0%

题解 P5492 [PKUWC2018]随机算法

发表于 更新于 分类于 ， Valine：

题目

数据范围 \(n\le20\)，集合/图上问题，考虑状压 DP

思路

对于集合的最大独立集 \(S\) 的各个点，有 \(|S|!\) 种放进独立集的顺序

生成点集：\(S\) 一个最大的点集 \(T\)，满足 \(S\subseteq T\) 且不存在 \(T\) 的一个独立子集 \(U\) 满足\(S\subsetneq U\)

我的理解：最大独立集为 \(S\) 的最大的集合 \(T\)，是 \(S\) 的生成点集

对于每一个最大独立集的顺序 \(u_1, u_2,...u_{|S|}\)

\(u_1\) 必须第一个加入独立集，接下来所有 \(u_1\) 的邻点 \(to_{u_1}\) 安排的位置就随便了

\(\{u_1\}\) 的生成点集 \(gs(\{ u_1\} )\)（即 \(u_1\) 及其邻点）便处理完了

在剩余的点中，\(u_2\) 也必须第一个加入独立集

以此类推

形成独立集顺序为 \(u_1, u_2,...u_{|S|}\) 的概率为： \[ \prod_i^{|S|} \frac{1}{n-|gs(S_{i-1})|} \] 接下来可以 DP 了

设 \(f_S\) 表示集合 \(S\) 用该算法形成最大独立集的概率 \[ \large f_S=\sum_{i\in S}\frac{f_{S-\{ i\} }}{n-|gs(S-\{ i\} )|} \] 初值 \(f_{\varnothing}=1\)

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

template<typename T> inline void read(T &x) {}

const int N = 25;
const int M = (1 << 20) + 9;
const int MOD = 998244353;

int n, m, maxn, maxis, ans;
int to[N], map[M], size[M], gs[M], f[M], inv[N];
// to邻点，map见下，size集合大小，gs生成点集
bool is[M];// 是否是独立集

inline void main() {
    read(n), read(m);
    maxn = 1 << n;
    for (int i = 1, u, v; i <= m; ++i)
        read(u), read(v), to[u] |= 1<<(v-1), to[v] |= 1<<(u-1);
    for (int i = 1; i <= n; ++i)
        map[1<<(i-1)] = i;
    is[0] = true;
    for (int s = 1; s < maxn; ++s) {
        int x = s & -s, t = s ^ x;
        x = map[x], gs[s] = size[s] = size[t] + 1;
        if (is[t] && !(t & to[x]))
            is[s] = true, maxis = max(maxis, size[s]);
        for (int i = 1; i <= n; ++i)
            if (s & to[i])
                gs[s]++;
    }
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD%i] % MOD;
    f[0] = 1;
    for (int s = 1; s < maxn; ++s)
        if (is[s]) {
            for (int i = 1, x, t; i < maxn; i <<= 1)
                if (s & i) {
                    t = s ^ i;
                    f[s] = (1ll * f[t] * inv[n - gs[t]] % MOD + f[s]) % MOD;
                }
            if (size[s] == maxis)
                ans = (ans + f[s]) % MOD;
        }
    printf("%d\n", ans);
    return 0;
}