LOJ2290 [THUWC2017]随机二分图

题意：给定左右各 $n$ 个点的二分图和 $m$ 种边，每一种边有三种情况：

1. 这种边只有一条，有 $50\\%$ 的概率出现。
2. 这种边有两条，同时出现或者不出现，概率均为 $50\\%$。
3. 这种边有两条，分别出现，概率均为 $50\\%$。

求完美匹配的期望数量，对 $10 ^ 9 + 7$ 取模。$n\leq 15$。

首先考虑拆期望贡献，变为每一种完美匹配的出现概率之和。

我们直接考虑 DP，记 $f(S, T)$ 表示左边已选集合为 $S$，右边已选集合为 $T$ 的时候的期望数量。枚举不在 $S$ 中的最小元素和谁匹配即可，如果出现 2、3 类边，直接暴力转移。复杂度 $O(2 ^ {2n})$，实际由于 $S$ 的情况很少，可以通过。

这个做法看似很对，但是在处理 2 和 3 类边的时候会出现一些问题。具体的，虽然我们可能同时出现了两条边，但是在最后的完美匹配中的边可能只有一条，这样的话这种方法就不太可行。

我们容易发现如果我们只考虑两条边中的一条，他的出现概率就是 $50\\%$，只不过会在两条边同时出现的时候出现一些问题。我们先不管这个条件，按照 1 类边的表针任意选择两条边，这样在不选边和选一条边都是正确的。唯一不正确的就是当两条边同时存在时，这个概率并不是 $25 \\%$。2 类边是 $50\\%$ 的概率，所以我们钦定强制选这两条边，并钦定同时出现的概率为 $25\\%$。3 类边同理。

这样我们可以在 $O(2 ^ {2n})$ 的时间内解决该问题，用记忆化搜索可以通过。

int Dp(int S, int T)
{
	if (S == tot && T == tot) return 1;
	if (mp[S].count(T)) return mp[S][T];
	int res = 0, le = __builtin_ctz(S ^ tot);
	for (int ri = 0; ri < n; ++ ri)
	{
		if ((T >> ri & 1) || typ[le][ri] == -1) continue;
		// std::cout << S << ' ' << T << ' ' << (S | (1 << le)) << ' ' << (T | (1 << ri)) << '\n';
		res = (res + Dp(S | (1 << le), T | (1 << ri)) * (Mod + 1LL) / 2) % Mod;
		auto [u, v] = pr[le][ri];
		if (u == le || v == ri || (S >> u & 1) || (T >> v & 1)) continue;
		// std::cout << S << ' ' << T << ' ' << (S | (1 << le) | (1 << u)) << ' ' << (T | (1 << ri) | (1 << v)) << '\n';
		if (typ[le][ri] == 1)
			res = (res + Dp(S | (1 << le) | (1 << u), T | (1 << ri) | (1 << v)) * (Mod + 1LL) / 4) % Mod;
		if (typ[le][ri] == 2)
			res = (res + Dp(S | (1 << le) | (1 << u), T | (1 << ri) | (1 << v)) * (Mod - (Mod + 1LL) / 4)) % Mod;
	}
	return mp[S][T] = res;
}