自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:26:40，当前版本为作者最后更新于2022-02-17 17:03:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种干爆 std 的 $O(3^n)$ 做法。

设 $f_S$ 为 $S$ 中点集构成一个连通块的概率。

则有套路容斥：考虑这个点集不是连通块时，枚举其中一个点所在的连通块，要求这个连通块自己连通，并且和剩余的点之间没有边。

可以得到转移式：

其中 $F(S,T)$ 是 $S$ 与 $T$ 之间没有边的概率。

暴力计算将得到一个 $O(3^nn^2)$ 的做法。

考虑折半：预处理出 4 个数组 $s_{0/1,0/1}$，分别为：

• 所有 $[0,n/2)$ 中的点的子集 到 所有 $[0,n/2)$ 中的点的子集 之间没有边的概率
• 所有 $[0,n/2)$ 中的点的子集 到 所有 $[n/2,n)$ 中的点的子集 之间没有边的概率
• 所有 $[n/2,n)$ 中的点的子集 到 所有 $[0,n/2)$ 中的点的子集 之间没有边的概率
• 所有 $[n/2,n)$ 中的点的子集 到 所有 $[n/2,n)$ 中的点的子集 之间没有边的概率

这样暴力预处理这 4 个数组的时间是 $O(2^nn^2)$，同时可以通过拆分集合，把对应的 $s$ 相乘来 $O(1)$ 查询 $F(S,T)$。

如此继续暴力执行 DP 即可做到 $O(3^n)$，而且常数很小。这一做法可以推广到类似的状压连通块的题目，且均可以做到 $O(2^nn^2+3^n)$。

实战效果：在目前数据范围下最大的测试点可以比 std 快 20 倍左右。

#include <bits/stdc++.h>
using namespace std;

int n, S;
long double s[2][2][1<<7][1<<7], dp[1<<14], p[14][14];

inline void Read() {
	cin >> n;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) cin >> p[i][j];
	}
}

inline void Prefix() {
	S = (n + 1) / 2;
	for (int f1 = 0;f1 < 2;f1++) {
		for (int f2 = 0;f2 < 2;f2++) {
			for (int i = 0;i < (1 << S);i++) {
				for (int j = 0;j < (1 << S);j++) {
					s[f1][f2][i][j] = 1;
					for (int k = 0;k < S;k++) {
						for (int l = 0;l < S;l++) {
							if (((i >> k) & 1) && ((j >> l) & 1)) s[f1][f2][i][j] *= 1 - p[k + f1 * S][l + f2 * S];
						}
					}
				}
			}
		}
	}
}


inline long double Query(int s1, int s2) {
	return s[1][1][s1 >> S][s2 >> S] * s[1][0][s1 >> S][s2 & ((1 << S) - 1)] * s[0][1][s1 & ((1 << S) - 1)][s2 >> S] * s[0][0][s1 & ((1 << S) - 1)][s2 & ((1 << S) - 1)];
}

inline void Solve() {
	for (int i = 1;i < (1 << n);i++) {
		dp[i] = 1;
		int t = i ^ (i & -i);
		for (int j = t;j;j = (j - 1) & t) dp[i] -= dp[i ^ j] * Query(i ^ j, j);
	}
	long double ans = 0;
	for (int i = 1;i < (1 << n);i++) ans += dp[i] * Query(i, ((1 << n) - 1) ^ i);
	cout << fixed << setprecision(11) << ans << endl;
}

int main() {
	Read();
	Prefix();
	Solve();
	return 0;
}