P5492 [PKUWC2018]随机算法

题目链接

容易想到压“选择了哪些点”和“哪些是当前独立集”这两个状态来转移。复杂度 \(O(n4^n)\) 沦为暴力。

然后发现第二维一定是第一维的子集，于是我们想法避掉一些不合法状态来枚举，复杂度 \(O(nk3^n)\)，其中 \(k\) 是避掉不合法状态用的方法所需的复杂度（例如用 map 是 \(O(\log...)\)），但是不管怎样也无法通过全部数据。

再仔细想想如何压状态。我们发现只要“选了哪些点”会导致我们不知道哪些能选，无法转移；只要“哪些是当前独立集”会导致我们根本无法确认当前状态。

考虑将“能选的点”代替“选了哪些点”，然后就可以通过批量转移的方法来解决该问题。

设 \(f[S][i]\) 表示与独立集以及当前独立集相连的点所组成的集合，且最大独立集大小为 \(i\) 的方案数。注意，这个状态已经为 \(S\) 分配好位置了，比如 \(01010\) 可能对应着 1__3_ 或者 3_1__ 之类的状态。

然后我们能自然地想到：（\(P\) 表示与 当前枚举的 \(S\) 外的点 \(u\) 相连 的点集，\(A\) 表示排列）

然后发现有些状态计重了。比如 1 4 2 6 3 5 可能先 1 _ 2 _ 3 _ ，再 1 4 2 6 3 5；也可能先 _ 4 _ 6 _ 5，再 1 4 2 6 3 5。因此我们需要外加一些限制。

我们枚举放当前第一个空位的数，即强制固定 \(u\) 到最靠前的空位置。这样，每一种方案将对应唯一的转移方式。

据此转移即可。

关键代码：

inline void init() {
	for (register int i = 1; i <= All; ++i)	siz[i] = siz[i - lowbit(i)] + 1;
	for (register int i = 0; i < n; ++i) {
		e[i][i] = 1;
		for (register int j = 0; j < n; ++j) if (e[i][j])//Attention!!!
			p[i] |= (1 << j);
	}
	int up = (N << 3) - 10;
	jie[0] = jieni[0] = 1;
	for (register int i = 1; i <= up; ++i)	jie[i] = jie[i - 1] * i % P;
	jieni[up] = quickpow(jie[up], P - 2);
	for (register int i = up - 1; i; --i)	jieni[i] = jieni[i + 1] * (i + 1) % P;
}
inline ll get_a(int n, int m) {
	return jie[n] * jieni[n - m] % P;//Attention!!!
}
int main() {
	read(n), read(m); All = (1 << n) - 1;
	for (register int i = 1; i <= m; ++i) {
		int u, v; read(u), read(v); --u, --v;
		e[u][v] = e[v][u] = true;
	}
	init();
	f[0][0] = 1; vis[0][0] = 1;
	for (register int s = 0; s < All; ++s)
		for (register int j = 0; j <= siz[s]; ++j) if (vis[s][j])
			for (register int k = 0; k < n; ++k) if (!((s >> k) & 1)) {
				ADD(f[s | p[k]][j + 1], 1ll * f[s][j] * get_a(n - siz[s] - 1, siz[p[k]] - siz[p[k] & s] - 1) % P);
				vis[s | p[k]][j + 1] |= vis[s][j];
			}
	int ans = 0;
	for (register int i = siz[All]; ~i; --i)
		if (vis[All][i]) {
			ans = f[All][i];
			break;
		}
	printf("%lld\n", jieni[n] * ans % P);
	return 0;
}

P5492 [PKUWC2018]随机算法

原文：https://www.cnblogs.com/JiaZP/p/13442495.html