自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 22:11:19，当前版本为作者最后更新于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})}$$

• $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]$ 之和

代码

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