题解 P7105 【「C.E.L.U-01」门禁】

· · 题解

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

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

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

可以得到转移式：

f_S=\sum_{T\subset S}f_TF(S\backslash T,T)

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

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

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

这样暴力预处理这 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;
}