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

xyz32768 · 2019-12-26 16:25:08 · 题解

• 写一发 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})}

• 推出这个式子之后，我们就有了一个 DP：

• f[\emptyset]=1
• f[S]=\sum_{i\in S}\frac{f[S-\{i\}]}{n-size(S-\{i\})}

• 最后的答案就是原图所有最大独立集 S 的 f[S] 之和

代码

#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;
}