Tony102's Blog - Min-Max 容斥
type: channel
link: https://tony102.com/index.php/tag/Min-Max-%E5%AE%B9%E6%96%A5/
items: Luogu3175 [HAOI2015]按位或
items: Min-Max 容斥学习笔记

Luogu3175 [HAOI2015]按位或
type: item
date: 2021-09-07T21:36:00+08:00
description: LinkSolmin-max 容斥题。还是利用了 min-max 容斥在期望下成立的性质。现在要求的是：$E(max\{T\})$ 。但是好求的是 $E(min\{T\})$ 。这也是 min-max 容斥入门题的基本套路。有：$$ E(min\{T\}) = \frac{1}{\sum\limits_{S\cap T \neq \emptyset} p(S)} $$只要任意一个 $S$ 与 $T$ 有交就至少会产生一个位。但是我不会。也许你会说，你会求超集。但是王总告诉你，对每一位取反后，就可以求子集。那么这个 $\sum$ 就可以用一个 FMT 预处理子集和解决。然后就用这个式子套 min-max 容斥的基本式子就可以了。Code#include <bits/stdc++.h> using namespace std; const int SIZE = (1 << 20) + 5; const double eps = 1e-7; int n, m; int cnt[SIZE]; double p[SIZE]; void FMT(double *a) { for (int a0 = 2, a1 = 1; a0 <= m; a0 <<= 1, a1 <<= 1) for (int i = 0; i < m; i += a0) for (int j = 0; j < a1; ++ j) a[i + j + a1] += a[i + j]; } int main() { scanf("%d", &n); m = (1 << n); for (int i = 0; i < m; ++ i) scanf("%lf", &p[i]), cnt[i] += cnt[i >> 1] + (i & 1); FMT(p); double ans = 0.00; for (int i = 1; i < m; ++ i) { if (1.00 - p[(m - 1) ^ i] < eps) return puts("INF"), 0; ans += ((cnt[i] & 1) ? 1.00 : -1.00) / (1 - p[(m - 1) ^ i]); } printf("%.7lf\n", ans); return 0; }

Min-Max 容斥学习笔记
type: item
date: 2021-09-05T11:40:00+08:00
description: 用途Min-Max容斥，又称最值反演，是一种对于特定集合，在已知最小值或最大值中的一者情况下，求另一者的算法。也就是说，如果知道最小值或者最大值，可以不通过比较求得另外一者。推导记 $Max(S)$ 为 $S$ 集合的最大值，$Min(S)$ 为 $S$ 集合的最小值。有：$$ Max(S) = \sum\limits_{T \subseteq S, T \neq \emptyset} f(|T|) Min(T) $$其中 $f(|T|)$ 使我们即将构造的一个容斥系数。Min-Max 容斥的主要工作就是构造该系数。考虑集合中每一个元素能不能给 $Max(S)$ 贡献。记 $n = |S|$，假设集合中的元素 $x_1, x_2, \dots,x_n$ 按照降序排序。我们先枚举第 $i$ 大的值对 $Max(S)$ 的贡献，也就是有多少个 $T \subseteq S$ 的最小值是 $S$ 的第 $i$ 大值。那么前面的 $i-1$ 个数均可以任选。这一部分的答案为：$$ \sum\limits_{j = 0}^{i-1} \binom{i-1}{j} f(j+1) $$最终只有可能 $x_1$ 有贡献。所以必有：$$ [i=1] = \sum\limits_{j=0}^{i-1} \binom{i-1}{j} f(j + 1) $$设 $F(i) = [i + 1= 1], G(i) = f(i + 1)$ ，那么：$$ F(i) = \sum\limits_{j=0}^{i} \binom{i}{j} G(j) $$对其进行二项式反演。回顾二项式反演一般公式（下一行公式中 $f, g$ 均与上述定义无关，仅仅用作复习二项式反演）：$$ f(n) = \sum\limits_{i=n}^{m} \binom{i}{n}g(i) \Leftrightarrow g(i)=\sum\limits_{i=n}^{m} (-1)^{i-n} \binom{i}{n} f(i) $$所以对 $F, G$ 进行二项式反演得到：$$ G(i) = \sum\limits_{j=0}^{i} (-1)^{i-j} \binom{i}{j} F(j) $$考虑到 $F(j)$ 仅在 $j=1$ 出值为 $1$ ，所以：$G(i) = (-1)^{i-1}$所以推出：$$ Max(S) = \sum\limits_{T \subseteq S,T \neq \emptyset} (-1)^{|T|-1}Min(T) $$应用有两件很重要的事。Min-Max 容斥在期望下成立 （主要应用：都出现的期望时间）Min Max 符号可以互换具体方法：记 $t_i$ 表示第 $i$ 个元素出现的时间：$Max(S)$ 表示 $S$ 中 $t$ 的最大值，即所有元素都出现的时间。$Min(S)$ 表示 $S$ 中 $t$ 的最小值，即至少有一个元素出现的时间。这两者中要已知一者，一般 $Min(S)$ 比较好求。当单位时间出现 $T$ 中至少一个概率为 $p$ ，则出现 $T$ 中至少一个的期望时间为 $\frac{1}{p}$然后即可求出 $Max(s)$例题HDU4336 Card Collector[Luogu3175 [HAOI2015]按位或](https://www.luogu.com.cn/problem/P3175)K-th Min-Max 容斥挖坑待填。