题目分析

本题要求计算在随机有向化过程中，有向图 $G'$ 的最小外向生成树存在且边权和等于原无向图 $G$ 的最小生成树边权和的概率。

关键观察 1. 最小生成树的性质：原图 $G$ 的最小生成树是唯一的（在边权互不相同的情况下），或者我们可以按照 Kruskal 算法的顺序处理边。

2. 外向生成树的条件：有向图 $G'$ 存在外向生成树当且仅当存在一个根节点，使得从该根节点可以到达所有其他节点。

3. 随机过程：每条边独立地以 $\frac{1}{4}$ 的概率变成双向边、$\frac{1}{4}$ 的概率变成单向边（两个方向之一）、$\frac{1}{4}$ 的概率消失。

算法标签

• 状态压缩动态规划

• 最小生成树 (MST)

• 容斥原理

• 图论计数

• 并查集

算法思路

主要步骤

1. 预处理：

• 读入图 $G$ 的边信息

• 计算 $2^k$ 的幂次，用于后续计算

• 初始化并查集

2. 按边权处理边：

• 将边按权值排序，模拟 Kruskal 算法过程

• 对于相同权值的边组，一起处理

3.状态压缩 DP：

• 使用位掩码表示节点子集

• 定义状态：

  • ans[s]：在节点集合 s 上形成合法外向生成树的方案数

  • f[s]：在连通分量 s 上形成特定结构的方案数

  • g[s]：用于容斥计算的辅助数组

4. 容斥原理：

• 通过容斥排除不形成外向树的情况

• 计算满足条件的方案数

5. 概率计算：

• 总方案数为 $4^m$（每条边有4种可能）

• 最终概率 = 合法方案数 / 总方案数，对 $10^9+7$ 取模

核心代码解析

// 状态转移关键部分
for (int s : ids) {
    g[s] = 0;
    // 容斥计算
    for (int t = (s - 1) & s; t; t = (t - 1) & s) {
        if (!(bel[t] & bel[s ^ t]) && __lg(s) == __lg(t)) {
            int cnt = cross(t, bel[s ^ t] ^ (s ^ t)) + 
                     cross(s ^ t, bel[t] ^ t) + 
                     num[bel[s] ^ s] - num[bel[t] ^ t] - num[bel[s ^ t] ^ (s ^ t)];
            (g[s] += mod - f[t] * g[s ^ t] % mod * pw[cnt] % mod) %= mod;
        }
    }
    f[s] = coef[s] * pw[num[bel[s]]] % mod;
    
    // 更新f[s]
    for (int t = s; t; t = (t - 1) & s) {
        if (!(bel[t] & bel[s ^ t])) {
            int cnt = cross(t, bel[s ^ t]) + num[bel[s] ^ t] - num[bel[t] ^ t];
            (f[s] += mod - g[t] * coef[s ^ t] % mod * pw[cnt] % mod) %= mod;
        }
    }
    (g[s] += f[s]) %= mod;
}

复杂度分析

• 状态数：$O(2^n)$，其中 $n \leq 15$

• 转移复杂度：$O(3^n)$（子集枚举）

• 总体复杂度：$O(3^n \cdot m)$，在题目限制下可接受

样例验证

样例1

• $n=2, m=1$：概率为 $\frac{3}{4} = 750000006 \pmod{10^9+7}$

• $n=3, m=3$：概率为 $\frac{51}{64} = 171875002 \pmod{10^9+7}$

与题目描述一致。

总结

本题通过状态压缩动态规划结合容斥原理，解决了有向图外向生成树与无向图最小生成树边权和相等的概率计算问题。算法充分利用了位运算优化和并查集维护连通性，在指数复杂度下解决了这一组合计数问题。

关键技巧：

1.按边权分组处理

2.状态压缩表示节点子集

3.容斥原理排除非法情况

4.并查集维护连通分量信息

该解法能够正确处理题目中的所有测试数据，包括各种特殊性质的情况。