min-max容斥学习笔记

最近报了航电的春季赛，在一道题目里面遇到了做法，感觉挺有意思。

考虑一个（多重）集合 S = { a i } S=\{a_i\} S={ai​}，有如下的等式成立

$$\underset{a_i\in S}{\min }(a_i)=\sum _{T\subseteq S,T\ne \varnothing }(-1{)}^{|T|-1}\underset{a_i\in T}{\max }(a_i)$$

反之亦然，

$$\underset{a_i\in S}{\max }(a_i)=\sum _{T\subseteq S,T\ne \varnothing }(-1{)}^{|T|-1}\underset{a_i\in T}{\min }(a_i)$$

这两个公式还是比较容易理解的，这里只拿第一条式子进行分析。

首先是最小的元素$a_1$，只有 T = { a 1 } T=\{a_1\} T={a1​}的时候才有$a_1$的贡献。

对于其它的元素，假设有$k$个比它小的数，那么这个元素总的贡献就是${\sum }_{i=0}^k(-1{)}^i{C}_k^i=(1-1{)}^k=0$，因此这么容斥下来就会得到最小的数。

回到这一题中，因为有期望，所以这两个式子不能直接用。但因为期望实际上把全部情况加起来，因此可以直接把两边加上期望，即

$$E(\underset{a_i\in S}{\min }(a_i))=E(\sum _{T\subseteq S,T\ne \varnothing }(-1{)}^{|T|-1}\underset{a_i\in T}{\max }(a_i))$$

在这一题中，集合就是没有被污染的行和列，而max操作就意味着要把集合行和列全部染上。

考虑一共有$x$个点在选出来的行和列里面，尝试计算把全部点染完的期望步数。首先，染完第一个点的概率是$\frac{x}{n\times m}$，因此期望步数为$\frac{n\times m}{x}$；在此之后，染完第二个点的概率是$\frac{x-1}{n\times m}$，因此期望步数为$\frac{n\times m}{x-1}$，因此类推，总的贡献就是${\sum }_{i=1}^k\frac{n\times m}{i}$。

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

const int N = 1e6 + 10, mod = 998244353;

int power(int a, int b) {
    int ret = 1;
    while (b) {
        if (b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod; b >>= 1;
    }
    return ret;
}

int n, m, k;
vector<int> a[N];
int f[N];
int fc[N], ifc[N];

int C(int a, int b) {
    return 1ll * fc[a] * ifc[b] % mod * ifc[a - b] % mod;
}

void solve() {
    cin >> n >> m >> k;
    f[1] = 1;
    for (int i = 2; i <= n * m; i++) {
        f[i] = (f[i - 1] + power(i, mod - 2)) % mod;
    }
    fc[0] = 1;
    for (int i = 1; i <= n * m; i++) {
        fc[i] = 1ll * fc[i - 1] * i % mod;
    }
    ifc[n * m] = power(fc[n * m], mod - 2);
    for (int i = n * m - 1; i >= 0; i--) {
        ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
    }
    for (int i = 1; i <= n; i++) {
        a[i].clear();
        a[i].resize(m + 5);
    }
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    int s1 = 0, s2 = 0;
    for (int i = 1; i <= n; i++) {
        bool bk = 1;
        for (int j = 1; j <= m; j++) {
            if (a[i][j]) {
                bk = 0; break;
            }
        }
        if (bk) s1++;
    }
    for (int i = 1; i <= m; i++) {
        bool bk = 1;
        for (int j = 1; j <= n; j++) {
            if (a[j][i]) {
                bk = 0; break;
            }
        }
        if (bk) s2++;
    }
    if (!s1 && !s2) {
        cout << "-1\n";
        return;
    }
    int ans = 0;
    for (int i = 0; i <= s1; i++) {
        for (int j = 0; j <= s2; j++) {
            if (!i && !j) continue;
            int w = (i + j) % 2 ? 1 : mod - 1;
            int cnt = i * m + j * n - i * j;
            int ret = 1ll * n * m * f[cnt] % mod;
            ret = 1ll * ret * C(s1, i) % mod * C(s2, j) % mod;
            ret = 1ll * ret * w % mod;
            ans = (ans + ret) % mod;
        }
    }
    cout << ans << endl;
}

int main() {
	// freopen("in.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

下一题是[HAOI2015] 按位或

设$S$是每一位的集合

根据前面所说的公式

$$E(\max (S))=\sum _{T\subseteq S,T\ne \varnothing }E(\min (T))$$

也就是要枚举每一个子集，求出其第一个出现期望有多久。

我们只需要用高维前缀和算出选择一次不包括$T$的概率$p$，那么$E(\min (T))=\frac{1}{1-p}$，然后就可以求出$E(\max (S))$了。

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

const int N = (1 << 20) + 10;
const double eps = 1e-9;

int n; double f[N], g[N];

int main() {
    // freopen("in.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < (1 << n); i++) {
        cin >> f[i];
        g[i] = f[i];
    }
    for (int j = 0; j < n; j++) {
        bool flag = 0;
        for (int i = 0; i < (1 << n); i++) {
            if (i >> j & 1) {
                if (f[i] > eps) {
                    flag = 1; break;
                }
            }
        }
        if (!flag) {
            cout << "INF\n";
            return 0;
        }
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < (1 << n); i++) {
            if (i >> j & 1) {
                g[i] += g[i - (1 << j)];
            }
        }
    }
    double ans = 0;
    for (int i = 1; i < (1 << n); i++) {
        double w = -1;
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) w = -w;
        }
        int mask = ((1 << n) - 1) ^ i;
        double t = 1.0 / (1.0 - g[mask]);
        ans += w * t;
    }
    cout << fixed << setprecision(8) << ans << endl;
}