min-max容斥

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

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

$\sum\limits_{sz=0}^{k-1}(-1)^{sz} \dbinom{k-1}{sz}$ 次

这里的 $sz$ 指的是除了元素 $x$ 以外，集合 $T$ 内其他的元素个数

而它又等于 $(1-1)^{k-1}=[k-1=0]=[k=1]$

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

有如下推论。

首先列出通项

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

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

这样变换的好处是把一个和 $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)$ 的形式，这样方便处理。

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

来看一道题目

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

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

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

而 $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$ 的时间集合。

同样有

然后就差不多了。

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

这里用了 $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)$

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