min-max容斥

· · 个人记录

min_max容斥无疑为 \min 和 \max 搭建了一座桥梁。

\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\min(T)

证明：对于 S 中元素 x，若其是第 k 大，则其被算了

这里的 $sz$ 指的是除了元素 $x$ 以外，集合 $T$ 内其他的元素个数 而它又等于 $(1-1)^{k-1}=[k-1=0]=[k=1]

也就是说除了最大的算一次，其他的都只算了 0 次

有如下推论。

\operatorname{lcm}(S)=\prod\limits_{T\subseteq S} \gcd(T)^{(-1)^{|T|-1}}

ARC202_C

首先列出通项

lcm(L_{a_1},L_{a_2},\cdots,L_{a_k})=\prod_{S\subseteq2^k} \gcd(L_S)^{(-1)^{|S|+1}}=\prod_{S\subseteq2^k} L_{\gcd(S)}^{(-1)^{|S|+1}}

那么 L_d 头顶上的指数应该是 \sum\limits_{\gcd(S)=d}(-1)^{|S|+1}，记其为 f(d)

然后看到 \gcd(S)=d 的条件应当立即想到做如下变换

g(d)=\sum\limits_{d|gcd(S)}(-1)^{|S|+1}

这样变换的好处是把一个和 S 里数字运算得出的值有关的量，变成了只和数字本身有关的量。

则有 f(d)=\sum\limits_{d|n} \mu(\frac{n}{d})g(n)

考察 g(d)，如果有 x 个数字被 d 整除，那么 g(d)=\sum\limits_{i=1}^x(-1)^{x+1}\dbinom{x}{i}

最后得到 g(x)=\begin{cases}1&x\geq1\\0&x=0\end{cases}

这样我们的解法就变得很明朗了。

首先 n\log n 把所有数的约数给处理好 (\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{n}\leq \log n)

加入 a_i ，如果之前没有出现过 a_i，那么在约数表里扫描。把对应的 g(d) 改成 1。然后再枚举 d 的约数，修改 f，修改 f 时对应修改 ans。

总结与启发：在高维取 \min 和取 \max 要可以从反方向想，使用 min_max 定理。碰到 \gcd(S) 要记得使用反演变成 d|\gcd(S) 的形式，这样方便处理。

E(\max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(\min(T))

不是很清楚怎么证……可能就是用期望的定义式吧

来看一道题目

给定 n*m的棋盘，每个格子上有 0 ~ 9 的数字。每个回合以的概率选中格子 (i,j) 并涂成黑色，可能重复涂色。若每行每列都至少有一个黑色格子则游戏结束。求结束的期望时间。

令集合 S 为所有行和列被第一次覆盖到的时间的集合。那么其子集 T 则代表了一部分行和列第一次被覆盖到的时间集合。

我们要求的应当是 E(\max(S))，于是发动某武功秘籍。

E(\max(S))=\sum\limits_{T\subseteq S} (-1)^{|T|+1} E(\min(T))

而 E(\min(T))

有 E(\min(T))=\sum\limits_{i=1} p(i)*i=\sum\limits_{i=1} p(step\geq i)=\sum\limits_{i=1}(1-p)^i=\frac{1}{p}=\frac{\sum\limits_{i=1}^n\sum\limits_{j=1}^m P_{i,j}}{\sum\limits_{(i,j)∈T}P_{i,j}}

这个 p 就是选到集合 T 里格子的概率。

我们发现 \sum\limits_{(i,j)∈T}P_{i,j} 是个较小的数字。并且它对应增加到答案的系数也只有 ±1 两种可能。

由于 nm\leq 150，所以 \max(n,m)\leq 12，不妨设 n\leq m

于是我们枚举行的子集。然后对于列，我们设计状态 f_{i,sum,coe} 代表前 i 列，概率总和为 sum，最终加到答案里系数为 coe 的方案总数。

时间复杂度：2^n*m*9nm=O(2^nnm^2)

还有一道题目 P3175 [HAOI2015] 按位或

对于这种期望题，我们的集合 S 不需要考虑期望意义，也就是说，只需要注意在一次的时候重要的东西（如怎么判定结束，怎么弄出 \min/\max 意义）在于什么即可。

我们令集合 S 为每一位被赋予 1 的时间集合。

同样有

E(\max(S))=\sum\limits_{T\subseteq S} (-1)^{|T|+1} E(\min(T))

然后就差不多了。

然后介绍一种类似于 ex min-max 的容斥

kthmax(S)=\sum\limits_{T\subseteq S} f(|T|-1)\min(T)

这里用了 f(|T|-1) 是想把要算的第 k 大的那个数排开来，这样的话，f 会更方便被表示

而我们该如何计算 f(|T|-1) 呢？

面对问题，我们要学会举一反三，方能一通百通

对于第 x 大的数字，它会被计算 g(x)=\sum\limits_{i=0}^{x-1} \dbinom{x-1}{i}f(i) 次

也就有 g(x+1)=\sum\limits_{i=0}^{x} \dbinom{x}{i}f(i)

而我们希望 g(x)=[x=k]

令 h(x)=g(x+1)=[x=k-1]

根据反演公式，我们有 f(x)=\sum\limits_{i=0}^{x}\dbinom{x}{i}(-1)^{x-i}h(i)=\sum\limits_{i=0}^{x}\dbinom{x}{i}(-1)^{x-i}g(i+1)=\dbinom{x}{k-1}(-1)^{x-k+1}

那么，我们有 kthmax(S)=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}\min(T)

这个式子对于期望同样成立！