[THUWC2017]随机二分图

传送门

题目

  某人在玩一个非常神奇的游戏。这个游戏中有一个左右各\(n\)个点的二分图,图中的边会按照一定的规律随机出现。

  为了描述这些规律,某人将这些边分到若干个组中。每条边或者不属于任何组 (这样的边一定不会出现),或者只属于一个组。

  有且仅有以下三类边的分组:

  这类组每组只有一条边,该条边恰好有\(50\%\)的概率出现。

  这类组每组恰好有两条边,这两条边有\(50\%\)的概率同时出现,有\(50\%\)的概率同时不出现。

  这类组每组恰好有两条边,这两条边恰好出现一条,各有\(50\%\)的概率出现。

  组和组之间边的出现都是完全独立的。

  某人现在知道了边的分组和组的种类,想要知道完美匹配数量的期望是多少。你能帮助她解决这个问题吗?

  数据范围详见原题。

题解

  这是一道与概率期望有关的一道题,比较难。

  最暴力的做法就是将所有的边的组合枚举,然后判断完美匹配数。太蠢了。

  枚举每个匹配,然后看这个匹配在多少种可能中出现过。当然,要判断匹配中是否存在冲突:比如说第三类边中,两个都存在就冲突了。复杂度\(\text{O}(n!\times m)\)。

  下面是正解:看到\(n\leq 15\),我们发现这个很可以状压:以\(n\)对点是否匹配上为状态,发现这样状态数为\(\begin{aligned}\sum_{i=0}^{n}{n\choose i}={2n \choose n}\end{aligned}\)种,当\(n=15\)时将近\(10^8\)。事实上大部分数据都跑不满。

  下一步呢?对以上每一组边进行分析。假设所有边都在第一类,则完美匹配数的期望实际上求的是这些边能够组成的完美匹配数\(\times (\dfrac{1}{2})^n\),落实到每一条匹配边,会贡献\(50\%\)的概率。

  对于第二种情况,强制了两条边要么同时出现,要么同时不出现,如果仍然按每条匹配边概率独立来看的话,一条边在匹配中的概率是\(50\%\),两条边都在匹配中的概率是\(25\%\),两条边都不在匹配中的概率为\(25\%\),最后一种并不重要,它并不会贡献到答案里。如果一条边在匹配中(注意这不等于只有这条边出现),则另一条边一定出现了且不在匹配之中,也就是说两条边一定都出现了,会贡献\(50\%\)的概率;而两条边都在匹配中同理也是会贡献\(50\%\)的概率,但现在却是\(25\%\),我们建立一个四元边,选它的概率为\(25\%\)(即一下子匹配掉这两条边)。从概率的角度来看,这两个事件是并列且独立的,加起来就是\(50\%\)了;

  对于第三种情况,与第二种情况很类似,只要将\(25\%\)调成\(-25\%\)即可。(因为两条边不可能会同时出现)

  最后小细节:为了避免重复计算,匹配需要按结点顺序枚举。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

#define ll long long
#define ull unsigned long long
#define min(a, b) (a) < (b) ? (a) : (b)
#define max(a, b) (a) > (b) ? (a) : (b)
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = a-1; ~i; --i)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

const int maxn = 16;
const int P = 1e9 + 7;

inline int read() {
    int w = 0, f = 1; char c;
    while (!isdigit(c = getchar())) c == '-' && (f = -1);
    while (isdigit(c)) w = w * 10 + (c ^ 48), c = getchar();
    return w * f;
}

int n, m;

std::unordered_map<int, int> f[1<<maxn]; // 用哈希表来优化内存
std::vector<std::pair<int, int> > E[maxn]; // 左边每个结点对应的边

int qpow(int a, int b) {
    int res = 1;
    for (int i = a; b; i = 1ll*i*i%P, b >>= 1)
        if (b & 1) res = 1ll*res*i%P;
    return res;
}

const int inv2 = qpow(2, P-2), inv4 = qpow(4, P-2);

void adde(int S, int P) { rep(i, 0, n-1) if (S&(1<<i)) return (void)E[i].push_back(std::make_pair(S, P)); } // 避免四元边重复计算,一定要return

int dp(int S) {
    if (!S) return 1; // 所有边匹配上返回
    int L = S&((1<<n)-1), R = S>>n;
    if (f[L].count(R)) return f[L][R]; // 记忆化
    int ans = 0, p = 0;
    while (!(S&(1<<p))) p++; // 找出编号最小的还没匹配上的结点
    rep0(i, E[p].size()) if ((E[p][i].first & S) == E[p][i].first) ans = (1ll*E[p][i].second*dp(S^E[p][i].first) + ans)%P; // 枚举S的子事件,然后乘上对应的概率
    return f[L][R] = ans; // 返回答案
}

int main() {
    n = read(), m = read();
    rep(i, 1, m) {
        int opt = read(), u = read(), v = read(), S = (1<<u-1) | (1<<v+n-1);
        adde(S, inv2); // 加入一条边
        if (opt) {
            int u1 = read(), v1 = read(), S1 = (1<<u1-1) | (1<<v1+n-1);
            adde(S1, inv2); // 加入另一条边
            if (!(S&S1)) adde(S ^ S1, opt == 1 ? inv4 : P-inv4); // 加入四元边。根据情况看概率
        }
    }

    printf("%d", 1ll*dp((1<<(n<<1))-1)*qpow(2, n)%P); // 注意最终答案为E*2^n%1e9+7

    return 0;
}
上一篇:850转租保利一期10栋05户型四房中的大次卧


下一篇:洛谷P4546 [THUWC2017]在美妙的数学王国中畅游 [LCT,泰勒展开]