Min-Max 容斥学习笔记

tony102

2021 年 09 月 05 日

2081 次浏览

暂无评论

1674字数

总结

## 用途

> 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)
$$

## 应用

有两件很重要的事。

1. Min-Max 容斥在期望下成立 （主要应用：都出现的期望时间）
2. 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](http://acm.hdu.edu.cn/showproblem.php?pid=4336)

[Luogu3175 [HAOI2015]按位或](https://www.luogu.com.cn/problem/P3175)

## K-th Min-Max 容斥

挖坑待填。

最后修改：2021 年 09 月 05 日

如果觉得我的文章对你有用，请随意赞赏

Min-Max 容斥学习笔记

tony102 • 2021 年 09 月 05 日

Min-Max 容斥学习笔记

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

SP1716 GSS3 - Can you answer these queries III

UOJ228. 基础数据结构练习题

CF515E Drazil and Park

ARC125E Snack

20210913 子段排序 (subarray)

Min-Max 容斥学习笔记

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Min-Max 容斥学习笔记

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款