自动搬运

查看原文

来自洛谷，原作者为

	duyi 大家好我是于之航爸爸

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

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

以下是正文

---

洛谷的latex有严重的问题，请务必在我的cnblogs查看本文！

链接

LOJ2290 「THUWC 2017」随机二分图

题目链接

本题题解

设完美匹配数量的期望是 $E$。根据期望的定义：

$$E = \sum_{一张图} (\text{这张图出现的概率})\times (\text{这张图的完美匹配数量}) $$

根据期望的线性性，可以转化为：

$$E = \sum_{一组完美匹配}(这组完美匹配出现的概率)$$

暴力做法，可以 $\mathcal{O}(n!)$ 枚举一组完美匹配，计算它出现的概率。

计算一组完美匹配出现的概率，只需要考虑这组完美匹配里的边。举个例子，你要求抛 $3$ 次硬币，前两次都是正面朝上的概率，这个概率就是 $\frac{1}{2} \cdot \frac{1}{2}$，而不需要考虑第三次的结果。同理，本题里，在计算时，只需要保证当前这组完美匹配里的边都在图上出现了，而其它边是否出现则不用管。

优化上述暴力。考虑使用状压 DP。当只有 $t = 0$ 时，可以设 $\mathrm{dp}_0(i, s)$，其中 $s$ 是一个二进制状态，表示考虑了左边的前 $i$ 个点，匹配掉了右边 $s$ 里这些点，发生的概率。转移时枚举左边第 $i + 1$ 个点匹配了右边的哪个点，乘上概率 $\frac{1}{2}$，进行转移。最后 $E = \mathrm{dp}_0(n, 2^n - 1)$。

当有 $t = 1$ 和 $t = 2$ 时，要注意到：题目限制了一组里两条边在图上的出现情况，但并未直接限制它们在完美匹配里的出现情况。例如：对于 $t = 1$ 的两条边 $(a_1, b_1),(a_2, b_2)$，它们在图上要么同时出现，要么同时不出现（这是题目要求的），但在完美匹配里，可能只有 $(a_1, b_1)$，或只有 $(a_2, b_2)$，或两个都有，或两个都没有（当然，根据前面的讨论，两个都没有时不用管，我们只计算出现了的边出现的概率）。也就是说，一条边出现在图里和出现在完美匹配里，是两回事，在接下来读题解时，不要把它们搞混了。

因为涉及到要同时加入两条边，我们把 DP 状态改一改。设 $\mathrm{dp}_1(s_1, s_2)$ 表示左边 $s_1$ 里这些点匹配了右边 $s_2$ 里这些点（$s_1, s_2$ 二进制下 $1$ 的个数相同）。但是转移时遇到麻烦了。例如我要考虑，【只有 $(a_1,b_1)$ 出现在完美匹配里】的情况，那这个状态相当于要带一个附件要求：在此后的转移里，不能单独选 $(a_2, b_2)$（否则就和【$(a_1, b_1)$，$(a_2, b_2)$ 同时出现在完美匹配里】这种情况重复了）。但是你又不好把这个附加要求写进 DP 状态里，于是就会算进去一些不该算的东西，导致答案错误。

怎么办？本题的精髓就在这里了。将一组 $t = 1$ 的两条边拆开！假装它们就是 $t = 0$ 的两组边。观察此时在计算答案时，会是什么效果：

• 如果在最终的完美匹配里只出现了 $(a_1, b_1)$，那在我们统计时它对概率的贡献是 $\frac{1}{2}$。它代表的实际情况是：$(a_1, b_1)$ 和 $(a_2, b_2)$ 都在图里，我们知道这种情况实际出现的概率也是 $\frac{1}{2}$。所以算的就是对的！
• 如果在最终的完美匹配里只出现了 $(a_2, b_2)$，和上一种情况同理。
• 如果在最终的完美匹配里，同时出现了 $(a_1, b_1)$ 和 $(a_2, b_2)$，则统计时对概率的贡献是 $\frac{1}{4}$。但是它代表的实际情况是 $(a_1, b_1)$ 和 $(a_2, b_2)$ 都在图里，我们知道这种情况出现的概率其实是 $\frac{1}{2}$。所以这里就少算了 $\frac{1}{4}$。怎么办？根据期望的线性性，我们单独把这少算的 $\frac{1}{4}$ 加回来就行了！所以我们新建一种转移，同时取 $(a_1,b_1)$ 和 $(a_2,b_2)$，且这种转移的系数是 $\frac{1}{4}$。
• 如果都没出现，不用管。

$t = 2$ 是类似的。【在最终的完美匹配里，同时出现了 $(a_1, b_1)$ 和 $(a_2, b_2)$】，这种情况在统计时对概率的贡献是 $\frac{1}{4}$，但实际上它发生的概率是 $0$。所以我们要想办法减掉这 $\frac{1}{4}$。新建一种系数是 $-\frac{1}{4}$ 的转移即可。

此外，一定不要把【相同的匹配、不同的加入顺序】当成不同的方案。解决的方法是转移时，强制选当前左边（$s_1$ 里）编号最小（或最大）的一个空点进行转移。

上述状压 DP，看起来时间复杂度是 $\mathcal{O}(2^{2n}\cdot n^2)$。但其实有了【$s_1, s_2$ 二进制下 $1$ 的个数相同】这个要求后，状态数从 $2^{2n}$ 减小至 $\sum_{i = 0}^{n}{n\choose i}^2 = {2n\choose n}\approx 1.5\cdot 10^8$。仍然有些大。但我们可以用 $\texttt{std::map}$ 存状态，使用记忆化搜索进行 DP，即可通过本题。

参考代码

放一个网上的，很好看的代码。

/*program by mangoyang*/
#pragma GCC optimize("Ofast", "inline")
#include<bits/stdc++.h>
#define inf ((int)(1e9))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int f = 0, ch = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int INV2 = 500000004, INV4 = 250000002, mod = 1e9 + 7;
map<int, int> f;
int a[300], b[300], n, m, cnt;

inline int Pow(int a, int b){
	int ans = 1;
	for(; b; b >>= 1, a = 1ll * a * a % mod)
		if(b & 1) ans = 1ll * ans * a % mod;
	return ans;
}

inline int dfs(int mask){
	if(mask == (1 << (n << 1)) - 1) return 1;
	if(f.count(mask)) return f[mask];
	int now = 0, tmp = 0;
	for(int i = n - 1; ~i; i--)
		if(!((1 << i) & mask)) now = (1 << i);
	for(int i = 1; i <= cnt; i++)
		if((now & a[i]) && !(mask & a[i]))
			(tmp += 1ll * dfs(mask | a[i]) * b[i] % mod) %= mod;
	return f[mask] = tmp;
}

int main(){
	read(n), read(m);
	for(int i = 1, op, x, y; i <= m; i++){
		read(op), read(x), read(y), x--, y--;
		int tmp = (1 << x) | (1 << y + n);
		a[++cnt] = tmp, b[cnt] = INV2;
		if(op){
			read(x), read(y), x--, y--;
			a[++cnt] = (1 << x) | (1 << y + n), b[cnt] = INV2;
			if(tmp & ((1 << x) | (1 << y + n))) continue;
			tmp |= (1 << x) | (1 << y + n);
			a[++cnt] = tmp, b[cnt] = op == 1 ? INV4 : -INV4 + mod;
		}
	}
	cout << 1ll * dfs(0) * Pow(2, n) % mod << endl;
	return 0;
}