问题形式化描述

我们有一个二分图 $G = (U, V, E)$，其中 $|U| = |V| = n$。边集 $E$ 被划分为若干组（每条边至多属于一组），每组边按以下规则随机出现：

1. 类型 0（$t=0$）：单边组 $\{e\}$，$P(e \text{出现}) = \frac12$。
2. 类型 1（$t=1$）：双边组 $\{e_1, e_2\}$，$P(e_1 \land e_2) = \frac12$，$P(\lnot e_1 \land \lnot e_2) = \frac12$。
3. 类型 2（$t=2$）：双边组 $\{e_1, e_2\}$，$P(e_1 \land \lnot e_2) = \frac12$，$P(\lnot e_1 \land e_2) = \frac12$。

组间独立。设 $X$ 为随机图 $G$ 的完美匹配数量，求：

$$E = \mathbb{E}[X], \quad \text{输出 } (2^n \cdot E) \bmod (10^9+7) $$

---

理论基础

1. 期望的线性性

设 $\mathcal{M}$ 为所有完美匹配的集合，对 $M \in \mathcal{M}$，定义指示变量：

$$I_M = \begin{cases} 1 & \text{若 } M \text{ 中所有边都出现} \\ 0 & \text{否则} \end{cases} $$

则：

$$X = \sum_{M \in \mathcal{M}} I_M, \quad E = \sum_{M \in \mathcal{M}} \mathbb{E}[I_M] = \sum_{M \in \mathcal{M}} P(I_M = 1) $$

---

2. 完美匹配出现的概率

对于匹配 $M$，定义事件 $A_M = \{\forall e \in M, e \text{ 出现}\}$。

由于组间独立：

$$P(A_M) = \prod_{g \in \mathcal{G}} P_g(M)$$

其中 $P_g(M)$ 表示组 $g$ 对 $M$ 的贡献概率。

分组贡献分析

• 类型 0：若 $e \in M$，则 $P_g(M) = \frac12$；否则 $P_g(M) = 1$。
• 类型 1：
  • 若 $\{e_1,e_2\} \subseteq M$，则 $P_g(M) = \frac12$（两条边同时出现）。
  • 若 $|\{e_1,e_2\} \cap M| = 1$，则 $P_g(M) = 0$（不可能只出现一条）。
  • 若 $\{e_1,e_2\} \cap M = \emptyset$，则 $P_g(M) = 1$。
• 类型 2：
  • 若 $\{e_1,e_2\} \subseteq M$，则 $P_g(M) = 0$（不可能同时出现两条）。
  • 若 $|\{e_1,e_2\} \cap M| = 1$，则 $P_g(M) = \frac12$（该边出现）。
  • 若 $\{e_1,e_2\} \cap M = \emptyset$，则 $P_g(M) = 1$。

---

动态规划解法

状态设计

设 $f(S, T)$ 表示：左部点集 $S \subseteq U$ 与右部点集 $T \subseteq V$ 已匹配时，所有匹配方式的概率和（即 $\sum P(\text{匹配 } M \text{ 且 } M \subseteq \text{已选边})$）。

初始：$f(\emptyset, \emptyset) = 1$。

目标：$f(U, V)$。

---

转移方程

选取 $x \in U \setminus S$ 作为当前要匹配的左部点，枚举与 $x$ 相关的边进行转移。

（1）单边转移（类型 0）

对每条类型 0 的边 $(x, y)$，若 $y \in V \setminus T$：

$$f(S \cup \{x\}, T \cup \{y\}) \leftarrow f(S \cup \{x\}, T \cup \{y\}) + \frac12 \cdot f(S, T) $$

（2）类型 1 的双边转移

对类型 1 的组 $\{(x,y), (u,v)\}$，若 $u \in U \setminus (S \cup \{x\})$ 且 $\{y,v\} \subseteq V \setminus T$：

$$f(S \cup \{x,u\}, T \cup \{y,v\}) \leftarrow f(S \cup \{x,u\}, T \cup \{y,v\}) + \frac14 \cdot f(S, T) $$

这里 $\frac14 = \frac12 \times \frac12$ 是因为：

• 选择 $(x,y)$ 作为匹配边贡献 $\frac12$（类型 0 部分）
• 同时 $(u,v)$ 也必须出现贡献另一个 $\frac12$
• 但两条边同时出现的概率是 $\frac12$（类型 1 的特性），所以总概率为 $\frac12 \times \frac12 = \frac14$

（3）类型 2 的双边转移

对类型 2 的组 $\{(x,y), (u,v)\}$，若 $u \in U \setminus (S \cup \{x\})$ 且 $\{y,v\} \subseteq V \setminus T$：

$$f(S \cup \{x,u\}, T \cup \{y,v\}) \leftarrow f(S \cup \{x,u\}, T \cup \{y,v\}) - \frac14 \cdot f(S, T) $$

这里使用负贡献 $- \frac14$ 是因为类型 2 的约束实际上排除了两条边同时出现的情况，在容斥框架下需要减去这种情况的贡献。

---

算法实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
const int inv2 = (MOD + 1) / 2;    // 1/2 mod MOD
const int inv4 = (MOD + 1) / 4;    // 1/4 mod MOD

int n, m;
vector<int> single_edges[15];           // t=0 的边
vector<pair<int, int>> type1_edges[15]; // t=1: (other_left, right_mask)
vector<pair<int, int>> type2_edges[15]; // t=2: (other_left, right_mask)
unordered_map<int, int> dp[1 << 15];    // dp[S][T] = f(S, T)

int solve(int S, int T) {
    if (S == 0) return 1;  // 所有点已匹配
    
    if (dp[S].count(T)) return dp[S][T];
    
    // 选取最低位的未匹配左部点
    int x = __builtin_ctz(S & -S);
    int res = 0;
    int new_S = S ^ (1 << x);
    
    // 处理单边 (t=0)
    for (int y : single_edges[x]) {
        if (T >> y & 1) {  // y 未匹配
            res = (res + 1ll * inv2 * solve(new_S, T ^ (1 << y))) % MOD;
        }
    }
    
    // 处理类型 1 的双边
    for (auto &[u, mask] : type1_edges[x]) {
        if ((new_S >> u & 1) && ((T & mask) == mask)) {
            // u 未匹配，且 mask 中的所有右部点未匹配
            res = (res + 1ll * inv4 * solve(new_S ^ (1 << u), T ^ mask)) % MOD;
        }
    }
    
    // 处理类型 2 的双边  
    for (auto &[u, mask] : type2_edges[x]) {
        if ((new_S >> u & 1) && ((T & mask) == mask)) {
            // 减去两条边同时出现的非法情况
            res = (res + 1ll * (MOD - inv4) * solve(new_S ^ (1 << u), T ^ mask)) % MOD;
        }
    }
    
    return dp[S][T] = res;
}

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int t, a, b, c, d;
        cin >> t >> a >> b;
        a--; b--;
        
        if (t == 0) {
            single_edges[a].push_back(b);
        } else {
            cin >> c >> d;
            c--; d--;
            
            // 将双边拆分为两条单边
            single_edges[a].push_back(b);
            single_edges[c].push_back(d);
            
            // 如果两条边端点不同，则记录组信息
            if (a != c && b != d) {
                // 保持 a < c 避免重复
                if (a > c) {
                    swap(a, c);
                    swap(b, d);
                }
                int mask = (1 << b) | (1 << d);
                if (t == 1) {
                    type1_edges[a].emplace_back(c, mask);
                } else { // t == 2
                    type2_edges[a].emplace_back(c, mask);
                }
            }
        }
    }
    
    int full_mask = (1 << n) - 1;
    int expected = solve(full_mask, full_mask);
    
    // 输出 2^n * E mod MOD
    for (int i = 0; i < n; i++) {
        expected = (expected * 2ll) % MOD;
    }
    
    cout << expected << endl;
    return 0;
}

---

复杂度分析

• 状态数：$O(2^n \times 2^n)$ 理论最坏，但实际可达状态远少于理论值。
• 转移代价：$O(\text{度数})$ 对于每个状态。
• 可行性：$n \leq 15$ 时，实际运行效率可以接受。

---

总结

本题通过状态压缩动态规划结合概率计算，巧妙地处理了带约束的二分图完美匹配期望问题。核心在于将复杂的概率约束转化为 DP 转移时的系数调整，利用记忆化搜索避免重复计算，最终在合理复杂度内求解。

该解法充分体现了组合数学与动态规划在概率期望问题中的强大应用。