Hall 定理还在追杀我

Priestess_SLG · 2026-08-10 22:30:13 · 题解

先回顾一下 Hall 定理：

对一张二分图 G 而言，设其左部点集合为 V_1，右部点集合为 V_2，则其存在大小为 |V_1| 的最大匹配当且仅当 \forall S\subseteq V_1\Longrightarrow |S|\le |N(S)|。

这里给出 Hall 定理的一个推论；

对一张二分图 G，设其左部点集合为 V_1，右部点集合为 V_2，则其最大匹配大小为 |V_1|-\max\limits_{S\subseteq V_1}(|S|-|N(S)|)。

对一个左部点集合 S，考虑记 v(S)=|S|-|N(S)|，则上面的最大匹配大小可以被表示为 |V_1|-\max\limits_{S\subseteq V_1}v(S)，因此问题可以被转化为求 \max\limits_{S\subseteq V_1}v(S) 的期望值是多少。

考虑对一个二分图，记这个二分图的好集合为其左部点集合的所有子集中，满足 \max\limits_{S\subseteq V_1}v(S)=v(S) 的集合 S。然后再定义极好集合为该二分图的所有好集合中，大小最小的集合。可以证明对任意二分图，都恰好存在一个极好集合。具体的：若两个不同的集合 A,B 都是极好集合，则其交集 A\cap B 也必然是极好集合，而显然有 |A\cap B|\le\min(|A|,|B|)。

然后考虑 dp。设 f_{S,T} 表示只考虑 S,T 两个点集内的点，以及一端在 S 集合内一端在 T 集合内的边时，把这张图看作是一个以 S 集合为左部点，T 集合为右部点的二分图中，若 S 集合的邻域恰好为 T 集合，而且存在一个匹配使得 S 集合中所有点都能匹配到 T 集合中的不同点的概率是多少；g_{S,T} 表示在上面的条件下，S 集合是该生成二分图的极好集合的概率是多少。

初始条件显然是 f_{0,0}=g_{0,0}=1。

为了方便转移，这里记 all_{S,T} 表示在上面的条件下，T 集合中的每个点都至少被 S 集合中某个点连到的概率是多少；noth_{S,T} 表示在上面的条件下，T 集合中的每个点都无法被 S 集合中的任意一个点连到的概率是多少。这两个东西是好处理的。具体来说：

然后考虑转移 f,g 两个 dp 数组。

先考虑第一个条件：S 点集的邻域恰好为 T，概率显然是 all_{S,T}。然后考虑容斥算不合法概率，如果某张图不能把 S 完全匹配，则其必然满足 \max\limits_{S'\subseteq S}v(S')\neq 0。取该左部点集唯一的极好集合 A\subseteq S 然后再设 B\subseteq T 是 A 集合的邻域，则此时一定有 |A|>|B|。A 是左部点集唯一的极好集合的概率就是 g_{A,B}，然后还需要保证 B 集合是 A 集合的完整邻域，所以 A 集合不能有边连向 T\backslash B，概率就是 noth_{A,T\backslash B}。删掉 A,B 两个点集后，剩下的部分 S\backslash A 必须能完全匹配到 T\backslash B，所以还需要额外乘 f_{S\backslash A,T\backslash B}。

总结一下，f 数组的转移就是 f_{S,T}=all_{S,T}-\sum\limits_{A,B}g_{A,B}\times f_{S\backslash A,T\backslash B}\times noth_{A,T\backslash B}，限制条件是 A\subseteq S,B\subseteq T,|A|>|B|。

然后考虑转移 g 数组。同样先从邻域恰好为 T 的图开始，也就是 all_{S,T}。同样考虑容斥，如果 S 集合不是极好集合，则说明其一定存在一个真子集 A\subset S 为极好集合。设 A 集合的邻域为 B，则为了让 S 不是极好集合，必须有 |A|-|B|\ge d。确定 A,B 两个集合后，同样还是分开算贡献，A 集合成为极好集合的概率为 g_{A,B}，然后 A 集合不能有边连向 T\backslash B，概率为 noth_{A,T\backslash B}，剩下的 S\backslash A 必须能够完全匹配到 T\backslash B 所以还需要额外乘 f_{S\backslash A,T\backslash B}。

总结一下，g 数组的转移就是 g_{S,T}=all_{S,T}-\sum\limits_{A,B}g_{A,B}\times f_{S\backslash A,T\backslash B}\times noth_{A,T\backslash B}，不一样的地方是限制条件为 A\subset S,B\subseteq T,|A-|B|\ge |S|-|T|。

转移这两个数组的时候直接一起转移即可。

最后考虑怎么统计答案。设整张图的极好集合为 S，S 集合在整张图中的邻域集合为 T，则此时 \max\limits_{S'\subseteq S}v(S)=|S|-|T| 因此该图的最大匹配大小就是 n-|S|+|T|。为了保证 S 在整张图上的邻域恰好还是 T 集合，需要保证 S 集合不连向 U_R\backslash T 集合，因此概率需要乘 noth_{S,U_R\backslash T}。然后考虑剩下的左部点部分 U_L\backslash S，她们必须能够值用二分图右部点中的剩余点 U_R\backslash T 来完全匹配。一位内不知道具体连到了哪些剩余的右部点，因此考虑再次枚举这个邻域 T'\subseteq U_R\backslash T。这个部分邻域恰好为 T' 且能够完全匹配的概率是 f_{U_L\backslash S,T'}，同时还需要保证这些点都不连向集合 U_R\backslash T\backslash T' 因此还需要额外乘以 noth_{U_L\backslash S,U_R\backslash T\backslash T'}。

总结一下，这一类二分图度对答案的贡献可以表示为 g_{S,T}\times noth_{S,U_R\backslash T}\times f_{U_L\backslash S,T'}\times noth_{U_L\backslash S,U_R\backslash T\backslash T'}\times (n-|S|+|T|)。枚举所有的集合 S,T,T' 然后把所有贡献相加即可得到最终的答案。

该算法的时间复杂度为 O(3^{n+m})，可以通过该题。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int p[610][610], tmp[610][610], all[610][610], noth[610][610], cnt[610], f[610][610], g[610][610];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m; cin >> n >> m;
    const int inv100 = inversion(100);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) cin >> p[i][j], p[i][j] = p[i][j] * inv100 % mod;
    for (int i = 0; i < n; i++) {
        tmp[i][0] = 1;
        for (int t = 1; t < (1 << m); ++t) {
            int j = __builtin_ctz(t);
            tmp[i][t] = tmp[i][t ^ (1 << j)] * (1 - p[i][j] + mod) % mod;
        }
    }
    for (int t = 0; t < (1 << m); ++t) noth[0][t] = 1;
    for (int s = 1; s < (1 << n); ++s) {
        int i = __builtin_ctz(s), pre = s ^ (1 << i);
        for (int t = 0; t < (1 << m); ++t) noth[s][t] = noth[pre][t] * tmp[i][t] % mod;
    }
    for (int s = 0; s < (1 << n); ++s) {
        all[s][0] = 1;
        for (int t = 1; t < (1 << m); ++t) {
            all[s][t] = 1;
            for (int S = t; S; S = (S - 1) & t) all[s][t] = (all[s][t] + mod - all[s][t ^ S] * noth[s][S] % mod) % mod;
        }
    }
    for (int s = 0; s < (1 << n); ++s)
        for (int t = 0; t < (1 << m); ++t) f[s][t] = g[s][t] = 0;
    f[0][0] = g[0][0] = 1;
    for (int s = 1; s < (1 << n); ++s) {
        for (int t = 0; t < (1 << m); ++t) {
            if (__builtin_popcount(s) > __builtin_popcount(t)) {
                g[s][t] = all[s][t];
                for (int a = (s - 1) & s; ; a = (a - 1) & s) {
                    for (int b = t; ; b = (b - 1) & t) {
                        if (__builtin_popcount(a) - __builtin_popcount(b) >= __builtin_popcount(s) - __builtin_popcount(t)) g[s][t] = (g[s][t] + mod - g[a][b] * f[s ^ a][t ^ b] % mod * noth[a][t ^ b] % mod) % mod;
                        if (!b) break;
                    } if (!a) break;
                }
            } else {
                f[s][t] = all[s][t];
                for (int a = s; a; a = (a - 1) & s)
                    for (int b = t; ; b = (b - 1) & t) {
                        if (__builtin_popcount(a) > __builtin_popcount(b)) f[s][t] = (f[s][t] + mod - g[a][b] * f[s ^ a][t ^ b] % mod * noth[a][t ^ b] % mod) % mod;
                        if (!b) break;
                    }
            }
        }
    }
    int res = 0;
    for (int s = 0; s < (1 << n); ++s)
        for (int t = 0; t < (1 << m); ++t)
            for (int t0 = (((1 << m) - 1) ^ t);; t0 = (t0 - 1) & (((1 << m) - 1) ^ t)) {
                res = (res + g[s][t] * noth[s][(((1 << m) - 1) ^ t)] % mod * f[((1 << n) - 1) ^ s][t0] % mod * noth[((1 << n) - 1) ^ s][(((1 << m) - 1) ^ t) ^ t0] % mod * (n - __builtin_popcount(s) + __builtin_popcount(t)) % mod) % mod;
                if (!t0) break;
            }
    cout << res << '\n';
}

} // namespace lowspeed_song

:::