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 容斥 笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南