BZOJ5006 [THUWC2017] 随机二分图

Description

有一个左右各 \(n\) 个点的二分图。有 \(m\) 组有概率出现的边,分为三种:

  1. 一组一条边,出现或不出现的概率各有 50%。
  2. 一组两条边,同时出现或同时不出现的概率各有 50%。
  3. 一组两条边,必定会恰好出现一条,概率各有 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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;
}