min-max容斥学习笔记

  • 前置知识

    二项式反演

    [f(n)=sum_{i=0}^nbinom{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_{varnothingnot=Ssubseteq T}(-1)^{|T|-1}min(T) ]
  • 证明

    首先我们先设一个容斥系数(f(x))

    [max(S)=sum_{varnothingnot=Ssubseteq 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}^nbinom{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_{varnothingnot=Ssubseteq T}(-1)^{|T|-1}min(T) ]
  • 用处

    在期望意义下,这个式子依然成立,即

    [E(max(S))=sum_{varnothingnot=Ssubseteq T}(-1)^{|T|-1}E(min(T)) ]

    下面给几个例题

  • 例题

    • HDU4336

      题意:有(n)个卡牌,每秒有(p_i)的概率抽到卡牌(i),求至少得到每个卡牌至少一张的期望时间

      min-max容斥有个套路思想就是化max为min,因为min一般比较好统计

      (max (S))表示集合(S)中最后一个获得元素的期望时间,(min (S))代表集合(S)中第一个获得元素的期望时间

      那么有上面的套路式子

      [max(S)=sum_{varnothingnot=Ssubseteq T}(-1)^{|T|-1}min(T) ]

      (min (T))就非常好求了

      [min(T)=frac{1}{sum_{iin T}p_i} ]

      就是先把总概率算一下的事情

    • 「HAOI2015」按位或

      题意:初始有一个数(0),每秒有(p_i)的概率或(|)上整数(i(iin [0,2^n))),求期望多少秒后数组变成(2^n-1)

      (max(S))表示最后一个或上去的期望时间,(min(S))同理

      式子随便套,考虑求出(min(T))

      [min(T)=frac{1}{sum_{Scap Tnot=varnothing}p_S} ]

      考虑求底下的东西

      [begin{aligned} sum_{Scap Tnot=varnothing}p_S&=sum_{Ssubseteq U} p_S-sum_{Scap T=varnothing}p_S\ &=sum_{Ssubseteq U}p_S-sum_{overline Scup T=overline S}p_S end{aligned} ]

      后面的东西取补集后是子集和的形式,我们可以(FWT)或者(FMT)(2^nn)内求出

    • 「PKUWC2018」随机游走

      题意:树上随机游走,给定起点,每次询问至少走过一次点集的期望时间

      直接套路上去考虑如何求(min (T)),即第一次到达给定点集的期望步数

      (dp_u)表示(u)走到给定点集(S)的期望步数,(d_u)(u)点度数

      (uin 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^nlog 998244353)处理出每个集合的(min(S))了,仍然可以预处理子集和

  • kthmax-min容斥

    [kthmax(S)=sum_{varnothingnot=Tsubseteq 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}^nbinom{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} ]
  • 参考资料

    【Learning】min-max容斥以及推广kth min-max容斥

    min-max容斥

内容来源于网络如有侵权请私信删除