min-max 容斥 笔记

2022/3/8 6:17:58

本文主要是介绍min-max 容斥 笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

min-max 容斥 笔记

前言

min-max 容斥是一类特殊的容斥形式,其特殊性在于各种数值与计数的结合。

一般来说,在解题时,如果一些值的 \(\min\) 不好算,而这些值的 \(\max\) 相对好算(或者相反),

则这时我们可以使用 min-max 容斥,在两种不同的问题形式间进行转换。

一. 定义式

对一个数集 \(S\),我们定义 \(\max(S)\) 为 \(S\) 中最大的元素值,\(\min(S)\) 为 \(S\) 中最小的元素值。

则对任意数集 \(S\),我们都有以下恒等式成立:

\(\large\max(S)=\sum\limits_{T\subseteq S,T\ne\varnothing}(-1)^{|T|-1}\min(T)\)。

二. 证明

我们用类似待定系数法的思想证明以上恒等式。

设 \(\max(S)=\sum\limits_{T\subseteq S,T\ne\varnothing}f(|T|)\min(T)\),其中 \(f\) 是我们需要解的容斥系数。

考虑将 \(\max(S)\) 拆解,即 \(\max(S)=\sum\limits_{u\in S}ux_{S,u}\),其中 \(x_{S,u}=[u=\max(S)]\)。

我们也将 \(\min(S)\) 拆解,即 \(\min(S)=\sum\limits_{u\in S}uy_{S,u}\),其中 \(y_{S,u}=[u=\min(S)]\)。

那么,对 \(\forall u\in S\),我们必须有 \(x_{S,u}=\sum\limits_{T\subseteq S,T\ne\varnothing}f(|T|)y_{T,u}\),

否则我们取 \(S\) 为一组基底(例如一组超越数组成的集合),就能让 \(f\) 不满足其定义。

我们设 \(u\) 是数集 \(M\) 中第 \(r(M,u)\) 大的数(默认 \(u\in M\)),那么由 \(x\) 和 \(y\) 的定义,我们不难证明:

\([r(S,u)=1]=\sum\limits_{T\subseteq S,T\ne\varnothing}f(|T|)[r(T,u)=|T|]\)。

考虑有多少个大小为 \(i\) 的数集 \(T\subseteq S,T\ne\varnothing\),满足 \(r(T,u)=i\),用排列组合得有 \(\dbinom{r(S,u)-1}{i-1}\) 个。

此时,上面的等式已经只与 \(|T|\) 有关,则等式可以重新写成枚举 \(i\) 作为 \(S\) 子集大小的形式:

\([r(S,u)=1]=\sum\limits_{i=1}^{r(S,u)}\dbinom{r(S,u)-1}{i-1}f(i)\)。

记 \(m=r(S,u)-1\),我们可以写出一个简洁明了的形式:

\([m=0]=\sum\limits_{i=0}^{m}\dbinom{m}{i}f(i+1)\)。

记 \(g(i)=[i=0]\),发现上式具有二项式反演的形式,即:

\(g(m)=\sum\limits_{i=0}^{m}\dbinom{m}{i}Ef(i)\),

则由二项式反演,我们有:

\(Ef(m)=\sum\limits_{i=0}^m(-1)^{m-i}\dbinom{m}{i}g(i)\)。

整理一下,得:

\(f(m+1)=\sum\limits_{i=0}^m(-1)^{m-i}\dbinom{m}{i}[i=0]=(-1)^m\),故 \(f(m)=(-1)^{m-1}\)。

将容斥系数 \(f\) 带回原式,我们也就得到了我们要证明的恒等式。

三. 应用

例题ABC242H

做法

定义 \(x(i)\) 为点 \(i\) 被覆盖的期望操作次数,

则对集合 \(S\),令 \(\max(S)=\max\{x(u)|u\in S\}\),\(\min(S)=\min\{x(u)|u\in S\}\),

由期望的线性性,可得集合 \(S\) 也满足篇首的恒等式,那问题就转化为求以下式子的值:

\(max(U)=\sum\limits_{T\subseteq U,T\ne\varnothing}(-1)^{|T|-1}\min(T)\),其中 \(U\) 代表全集。

又因为,设 \(c(S)\) 为所有不包含 \(S\) 中任何点的区间数,则我们不难得到 \(\min(S)=\frac{M}{M-c(S)}\)。

故我们发现,所求式右边只与 \(c(T)\) 的值,以及 \(|T|\) 的奇偶性有关,而这两个值的值域都有限,

故这时考虑用 DP 解决问题。

记 \(f(i,j,flg)\) 代表,考虑了 \(U\) 中前 \(i\) 个点,此时有多少个 \(T\) 满足:

\(i\in T,c(T)=j,|T|\equiv flg\) \(\mod2\)。

我们人为地加一个点 \(n+1\),则答案就是 \(\sum\limits_{j,flg}(-1)^{flg}\frac{M}{M-j}f(n+1,j,flg)\)。

这样的时间复杂度是 \(O(N^3)\) 的,瓶颈在于转移时枚举上一个选取的点 \(k\)。

最后给出期望线性性的一种证明。

定义

\(E(X+Y)=E(X)+E(Y)\)

证明

\(E(aX)=\sum\limits_{i}ax_ip_i=a\sum\limits_{i}x_ip_i=aE(X)\)

取 \(a=\frac{X+Y}{X}\),我们有:

\(E(X+Y)=E(X\cdot\frac{X+Y}{X})\)

\(=\frac{X+Y}{X}\cdot E(X)=E(X)+\frac{Y}{X}E(X)\)

\(=E(X)+E(X\cdot\frac{Y}{X})=E(X)+E(Y)\)。



这篇关于min-max 容斥 笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程