题解 P5492 【[PKUWC2018]随机算法】

- 写一发 $O(2^n\times n)$ 的做法 - 定义独立集 $S$ 的**生成点集**为一个最大的点集 $T$ ，满足 $S\subseteq T$ 且不存在 $T$ 的一个独立子集 $U$ 满足 $S\subsetneq U$ - 显然我们有：**$S$ 是最大独立集的必要条件是其生成点集为全集** - 现在考虑如果已经知道了用随机算法生成的独立集，并且知道了这些点加入独立集的顺序，如何生成一个合法的随机序列 - 首先，独立集的第一个点 $u_1$ 必须在随机序列的第一位 - 可以发现这时候对于一个不在独立集内的点 $u$ ，如果存在边 $(u,u_1)$ ，那么 $u$ 在随机序列中的位置可以任意 - 为这些 $u$ 的位置安排好了之后，我们又能发现，独立集的第二个点 $u_2$ 必须在剩下的位置中的第一位 - 然后如果对于满足存在边 $(v,u_2)$ 而不存在边 $(v,u_1)$ 的点 $v$ ，也可以安排在剩下的任意位置 - 于是我们得出：一个随机序列合法的条件是对于所有的 $1\le i\le|S|$ ，都满足序列中删掉前 $i-1$ 个点的生成点集之后，$u_i$ 位于剩下的位置中的第一位 - 易得这个随机序列合法的概率是： - $$\prod_{i=1}^{|S|}\frac1{n-size(S_{i-1})}$$ - $size$ 为生成点集大小，$S_i$ 表示 $S$ 前 $u_1$ 到 $u_i$ 构成的点集 - 推出这个式子之后，我们就有了一个 DP： - $f[S]$ 表示插入独立集的前 $|S|$ 个点构成集合 $S$（顺序未定），对于所有 $|S|!$ 种顺序，上式的值之和 - $$f[\emptyset]=1$$ - $$f[S]=\sum_{i\in S}\frac{f[S-\{i\}]}{n-size(S-\{i\})}$$ - 最后的答案就是原图所有最大独立集 $S$ 的 $f[S]$ 之和 ## 代码 ```cpp #include <bits/stdc++.h> template <class T> inline void read(T &res) { res = 0; bool bo = 0; char c; while (((c = getchar()) < '0' || c > '9') && c != '-'); if (c == '-') bo = 1; else res = c - 48; while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + (c - 48); if (bo) res = ~res + 1; } template <class T> inline T Max(const T &a, const T &b) {return a > b ? a : b;} const int N = 23, M = (1 << 20) + 5, rqy = 998244353; int n, m, Cm, ix[M], pset[N], cnt[M], sze[M], maxs, f[M], inv[N], ans; bool is[M]; int main() { int x, y; read(n); read(m); while (m--) read(x), read(y), pset[x] |= 1 << y - 1, pset[y] |= 1 << x - 1; is[0] = 1; Cm = 1 << n; for (int i = 1; i <= n; i++) ix[1 << i - 1] = i; for (int S = 1; S < Cm; S++) { int T = S ^ (S & -S), i = ix[S & -S]; if (is[T]) is[S] = !(T & pset[i]); cnt[S] = sze[S] = sze[T] + 1; if (is[S]) maxs = Max(maxs, sze[S]); for (int i = 1; i <= n; i++) if (S & pset[i]) cnt[S]++; } f[0] = inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = 1ll * (rqy - rqy / i) * inv[rqy % i] % rqy; for (int S = 1; S < Cm; S++) { if (!is[S]) continue; for (int i = 1; i <= n; i++) { if (!((S >> i - 1) & 1)) continue; int T = S ^ (1 << i - 1); f[S] = (1ll * f[T] * inv[n - cnt[T]] + f[S]) % rqy; } if (sze[S] == maxs) ans = (ans + f[S]) % rqy; } return std::cout << ans << std::endl, 0; } ```