min-max容斥学习笔记
-
前置知识
二项式反演
\[
f(n)=\sum_{i=0}^n\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)
\] -
一些定义
\(\max (S),\min (S)\)表示分别集合\(S\)的最大，最小元素
套路式子
\[
\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)
\]-
证明
首先我们先设一个容斥系数\(f(x)\)
\[
\max(S)=\sum_{\varnothing\not=S\subseteq T}f(|T|)\min(T)
\]
设集合\(S\)有\(n\)个元素，我们讨论第\(k\)小元素的贡献
\[
\sum_{i=0}^{n-k}\binom{n-k}{i}f(i+1)=[n-k=0]
\]
就是当这个元素成为最小值时另外再选几个比它要大的元素的方案，如果这个元素不是最大元素，要求不贡献设
\[
F(n)=f(n+1),G(n)=[n=0]
\]
上式为
\[
G(n)=\sum_{i=0}^n\binom{n}{i}F(i)
\]
由二项式反演
\[
F(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}G(i)
\]
代回去
\[
\begin{aligned}
f(n+1)&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}[i=0]\\
&=(-1)^n\\
f(n)&=(-1)^{n-1}
\end{aligned}
\]
所以有
\[
\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)
\] -
用处
在期望意义下，这个式子依然成立，即
\[
E(\max(S))=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}E(\min(T))
\]
下面给几个例题 -
例题
-
题意：有\(n\)个卡牌，每秒有\(p_i\)的概率抽到卡牌\(i\)，求至少得到每个卡牌至少一张的期望时间
min-max容斥有个套路思想就是化max为min，因为min一般比较好统计
令\(\max (S)\)表示集合\(S\)中最后一个获得元素的期望时间，\(\min (S)\)代表集合\(S\)中第一个获得元素的期望时间
那么有上面的套路式子
\[
\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)
\]
\(\min (T)\)就非常好求了
\[
\min(T)=\frac{1}{\sum_{i\in T}p_i}
\]
就是先把总概率算一下的事情 -
题意：初始有一个数\(0\)，每秒有\(p_i\)的概率或(|)上整数\(i(i\in [0,2^n))\)，求期望多少秒后数组变成\(2^n-1\)
令\(\max(S)\)表示最后一个或上去的期望时间，\(\min(S)\)同理
式子随便套，考虑求出\(\min(T)\)
\[
\min(T)=\frac{1}{\sum_{S\cap T\not=\varnothing}p_S}
\]
考虑求底下的东西
\[
\begin{aligned}
\sum_{S\cap T\not=\varnothing}p_S&=\sum_{S\subseteq U} p_S-\sum_{S\cap T=\varnothing}p_S\\
&=\sum_{S\subseteq U}p_S-\sum_{\overline S\cup T=\overline S}p_S
\end{aligned}
\]
后面的东西取补集后是子集和的形式，我们可以\(FWT\)或者\(FMT\)在\(2^nn\)内求出 -
题意：树上随机游走，给定起点，每次询问至少走过一次点集的期望时间
直接套路上去考虑如何求\(\min (T)\)，即第一次到达给定点集的期望步数
令\(dp_u\)表示\(u\)走到给定点集\(S\)的期望步数，\(d_u\)为\(u\)点度数
若\(u\in S,dp_u=0\)
否则
\[
\begin{aligned}
dp_u&=\frac{dp_{fa}}{d_u}+\frac{\sum dp_v}{d_u}+1\\
&=A_udp_{fa}+B_u
\end{aligned}
\]
就先把环状的转移和其他的分开搞一下，那么
\[
dp_u=\frac{dp_{fa}}{d_u}+\frac{\sum A_vdp_u+B_v}{d_u}+1
\]
化简一下
\[
(1-\frac{\sum A_v}{d_u})dp_u=\frac{dp_{fa}}{d_u}+\frac{\sum B_v}{d_u}+1
\]
把左边除过去就可以了这样的话我们可以\(n2^n\log 998244353\)处理出每个集合的\(\min(S)\)了，仍然可以预处理子集和
-
-
kthmax-min容斥
\[
kthmax(S)=\sum_{\varnothing\not=T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)
\]
\(kthmax(S)\)表示集合中第\(k\)大的元素证明起来和普通的差不多
设一个容斥系数\(f(n)\),统计\(n\)个元素中第\(x\)小的贡献
\[
\sum_{i=0}^{n-x}\binom{n-i}{i}f(i+1)=[n-x+1=k]\\
\sum_{i=0}^n\binom{n}{i}f(i+1)=[n=k-1]\\
f(n+1)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}[i=k-1]\\
f(n)=(-1)^{n-k}\binom{n-1}{k-1}
\] -
参考资料