题解 P4547 【[THUWC2017]随机二分图】

· · 题解

题目

orz神仙题

考虑只有t=0的时候怎么做

其实等价于求完美匹配的个数，但是我们有一个更为一般的dp可以写，设dp_{S,T}表示在一左部点里匹配的点集是S，右部点里匹配的点集是T的期望完美匹配个数

我们可以枚举一条边(i,j)，表示当前匹配的边是(i,j)，于是就有

dp_{S,T}=\sum_{i\notin S,j\notin T,(i,j)\in E}dp_{S/i,T/j}\times p_{i,j} 但是这样求出来的东西好像不是很对，因为对于某一种完全匹配，我们按照不同的加边顺序算了多次，于是我们钦定一个加边顺序，比如先加入编号小的点，这样就不会算重 由于$|S|=|T|$，所以这样的复杂度是$\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}$，还是比较科学的 再来考虑$t>0$的情况 对于$t=1$的边组$(u,v,a,b)$，我们还是先把$(a,b),(u,v)$都加入边集出现的概率视为$\frac{1}{2}$；对于一组完美匹配，如果$(a,b),(u,v)$其中之一出现在了里面，那么我们算进去的概率是$\frac{1}{2}$，这符合题意：但是当$(a,b),(u,v)$都出现了，我们算的概率是$\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}$，但真实的出现概率却是$\frac{1}{2}

所以只有在这两条边都出现的情况下我们才会错误计算，于是我们加一条四元边(u,v,a,b)，出现概率为\frac{1}{4}，这样对于一组(a,b),(u,v)都出现的完美匹配，我们计算的概率就是\frac{1}{4}+ \frac{1}{4}=\frac{1}{2}，这样算就正确了。

同理，对于t=2的情况，我们加一条四元边(u,v,a,b)出现的概率为-\frac{1}{4}即可

代码

#include <tr1/unordered_map>
#include <bits/stdc++.h>
#define re register
using namespace std::tr1;
const int mod = 1e9 + 7, inv2 = 500000004, inv4 = 250000002, _inv4 = 750000005;
unordered_map<int, int> dp, f;
inline int qm(int x) { return x >= mod ? x - mod : x; }
int se[5005], sp[5005], n, m, M;
int dfs(int s) {
    if (!s)
        return 1;
    if (f[s])
        return dp[s];
    int res = 0;
    f[s] = 1;
    for (re int i = 1; i <= M; i++)
        if ((se[i] & s) == se[i] && se[i] > s / 2)
            res = qm(res + 1ll * sp[i] * dfs(se[i] ^ s) % mod);
    // printf("%d %d\n",s,res);
    return dp[s] = res;
}
int main() {
    scanf("%d%d", &n, &m);
    for (re int t, u, v, a, b, i = 1; i <= m; i++) {
        scanf("%d%d%d", &t, &u, &v);
        se[++M] = (1 << (u - 1)) | (1 << (v + n - 1));
        sp[M] = inv2;
        if (!t)
            continue;
        scanf("%d%d", &a, &b);
        se[++M] = (1 << (a - 1)) | (1 << (b + n - 1));
        sp[M] = inv2;
        if (se[M] & se[M - 1])
            continue;//当(a,b),(u,v)有交点的时候，由于不可能同时存在于完美匹配里，所以没有必要加入四元边
        se[M + 1] = se[M] | se[M - 1];
        sp[++M] = (t == 1 ? inv4 : _inv4);
    }
    // for(re int i=1;i<=M;i++) printf("%d %d\n",se[i],sp[i]);
    printf("%d\n", 1ll * (1 << n) * dfs((1 << (n + n)) - 1) % mod);
    return 0;
}