BZOJ5006 [THUWC2017] 随机二分图
Description
有一个左右各 $n$ 个点的二分图。有 $m$ 组有概率出现的边，分为三种：
- 一组一条边，出现或不出现的概率各有 50%。
- 一组两条边，同时出现或同时不出现的概率各有 50%。
- 一组两条边，必定会恰好出现一条，概率各有 50%。
组与组之间的概率是独立的。
问完美匹配的期望个数 $E$ ，输出 $2^nE \pmod {10^9+7}$ （显然是整数）。
Solution
期望是可加的。所以可以枚举每个完美匹配求出现的概率和。复杂度 $O(n*n!)$ ， 20pts 。
为什么要枚举完美匹配呢？能不能状压 DP 求 $f_{S1,S2}$ 表示左右边各剩下 $S1, S2$ 时完美匹配个数呢？
因为第 2, 3 种边不好统计。假设只有第 1 种边。$O(m\sum_{i=0}^n {n \choose i}^2)$ （由于好多状态其实访问不到所以复杂度其实是 O( 玄学 ) ），配合上面那个有 40pts 。
考虑有第 2, 3 种边。如果我枚举的匹配中，不存在某两条边在同一组，那么它的概率肯定是 $2^{-n}$ 。
那么我考虑暂时把第 2, 3 种边拆开成两条独立的边，看对答案有什么影响。
如果某个匹配同时用到了第 2 种边某组中的两条（两条边的端点显然互不相同），那么应该有 $\frac12$ 的概率。但是如果我把它看成独立的两条边的话就是 $\frac14$ 的概率。所以我新建“一条边”连着这 4 个点，出现概率为 $\frac14$ 。这样一来这个匹配就会被算两遍，每遍都有 $\frac14$ ，一共就是 $\frac12$ 。
同样的，如果某个匹配同时用到了某组第 3 种边的两条，那么它会多算 $\frac14$ 的概率。那么我新建“一条边”连接这 4 个点，出现概率为 $-\frac14$ 。（似乎很魔幻）这样就可以把多出来的那 $\frac 14$ 抵消掉了。
然后状压 DP 就好了。
状态开不下？开 map 啊！
map 太慢？ unordered\_map 手写 hash 表啊！
Code
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
namespace Hash{
const int Mod = 29999999;
int key[Mod], val[Mod];
int lastt, lasts;
bool count(int t) {
int s = t % Mod;
while (key[s] != t && key[s] != 0)
if (++s == Mod) s = 0;
lastt = t; lasts = s;
return key[s] == t;
}
int &query(int t) {
int s = t % Mod;
if (t == lastt) s = lasts;
else while (key[s] != t && key[s] != 0) if (++s == Mod) s = 0;
key[s] = t;
return val[s];
}
};
typedef long long LL;
const int N = 15;
const int mod = 1000000007;
const int M = 500;
int n, m, A[M], B[M], C[M];
int f(int S1, int S2) {
// E[S1,S2] * 2^|S|
if (S1 == 0) return 1;
if (Hash::count(S1 << n | S2)) return Hash::query(S1 << n | S2);
int &ans = Hash::query(S1 << n | S2) = 0, x = 0;
while ((S1 >> x & 1) == 0) ++x;
for (int i = 0; i < m; ++i)
if ((A[i] & S1) == A[i] && (B[i] & S2) == B[i] && (A[i] >> x & 1) == 1)
ans = (ans + f(S1 & ~A[i], S2 & ~B[i]) * C[i]) % mod;
return ans;
}
int main() {
int c;
scanf("%d%d", &n, &c);
while (c--) {
int t, x, y;
scanf("%d", &t);
if (t == 0) {
scanf("%d%d", &x, &y);
A[m] = 1 << (x - 1), B[m] = 1 << (y - 1), C[m++] = 1;
} else {
scanf("%d%d", &x, &y);
A[m] = 1 << (x - 1), B[m] = 1 << (y - 1), C[m++] = 1;
scanf("%d%d", &x, &y);
A[m] = 1 << (x - 1), B[m] = 1 << (y - 1), C[m++] = 1;
if (A[m - 1] != A[m - 2] && B[m - 1] != B[m - 2]) {
A[m] = A[m - 1] | A[m - 2], B[m] = B[m - 1] | B[m - 2];
C[m++] = (t == 1 ? 1 : -1);
}
}
}
printf("%d\n", (f((1 << n) - 1, (1 << n) - 1) + mod) % mod);
return 0;
}