[学习笔记] min-max容斥

结论及证明

给定集合$S$，$max(S)$为集合$S$中的最大值，$min(S)$为集合$S$中的最小值，则我们有一个式子：
$$max(S)=\sum _{T\subseteq S}(-1{)}^{|T|-1}\times min(T)$$不多说，直接开证（淦 ），首先我们设一个容斥系数$f(|T|)$使这个式子成立：
$$max(S)=\sum _{T\subseteq S}f(|T|)\times min(T)$$我们考虑$x+1$大的元素会被算多少次（也就是它作为最小值出现的时候），枚举$[1,x]$大怎么选：
$$\sum _{i=0}^{x}C(x,i)\times f(i+1)$$然后这个式子必须满足$x=0$时为$1$，其他时候为$0$：
$$[x==0]=\sum _{i=0}^{x}C(x,i)\times f(i+1)$$你可以发现这是一个二项式反演的这个形式：
$$f(n)=\sum _{i=0}^{n}C(n,i)\times g(i)\Rightarrow g(n)=\sum _{i=0}^n(-1{)}^{n-i}C(n,i)\times f(i)$$（如果你觉得系数对不上，你可以先把$f(i+1)$整体左移，套公式后再右移回来）那么：
$$f(x+1)=\sum _{i=0}^x(-1{)}^{x-i}C(x,i)\times [x==0]$$$$f(x+1)=(-1{)}^x$$$$f(x)=(-1{)}^{x-1}$$兄弟们，得证了！！！淦！！！

kth-minmax 反演

后来推了一下，和上面方法一样。

哥哥现在来推一下 $\mathtt{k}\mathtt{t}\mathtt{h}-\mathtt{m}\mathtt{i}\mathtt{n}\mathtt{m}\mathtt{a}\mathtt{x}$ 反演：

$$kthmax(S)=\sum _{|T|\ge k}(-1{)}^{|T|-k}(\genfrac{}{}{0ex}{}{|T|-1}{k-1})\min (T)$$

假设不知道这东西，我们设容斥系数为 $f(|T|)$：

$$kthmax(S)=\sum _{|T|\ge k}f(|T|)\min (T)$$

考虑第 $x+1$ 大的元素会被计算多少次（作为最小值）：

$$\sum _{i=k-1}^{x}C(x,i)\times f(i+1)$$

这个柿子必须满足 $x=k-1$ 的时候为 $1$，其他时候为 $0$：

$$[x=k-1]=\sum _{i=k-1}^{x}C(x,i)\times f(i+1)$$

先平移一下 $f$，令 $g(x)=[x=k-1],f^{\prime }(x)=f(x+1)$，如果 $x<k-1$ 就把 $f^{\prime }(x)$ 设置为 $0$：

$$g(x)=\sum _{i=0}^{x}C(x,i)\times f^{\prime }(i)$$

我直接一波二项式反演：

$$f^{\prime }(x)=\sum _{i=0}^x(-1{)}^{x-i}\cdot (\genfrac{}{}{0ex}{}{x}{i})\cdot g(i)=\sum _{i=0}^x(-1{)}^{x-i}\cdot \left(\genfrac{}{}{0ex}{}{x}{i}\right)\cdot [i=k-1]$$

$$f^{\prime }(x)=(-1{)}^{x-k+1}\cdot (\genfrac{}{}{0ex}{}{x}{k-1})$$

$$f(x)=(-1{)}^{x-k}\cdot (\genfrac{}{}{0ex}{}{x-1}{k-1})$$

例题

Card Collector

有$n$张卡片，每一次你有$p_i$的概率买到第$i$张卡。求买到所有卡的期望购买次数。
$n\le 20,\sum p_i\le 1$

设$max(S)$表示组成$S$的最后一个元素的出现时间，$min(S)$表示组成$S$的第一个元素的出现时间：
$$max(U)=\sum _{S\subseteq U}(-1{)}^{|S|-1}\times min(S)$$然后$min(S)$很容易算：
$$min(S)=\frac{1}{{\sum }_{i\in S}p[i]}$$

#include <cstdio>
#define db double
const int M = 1<<20;
int read()
{
    int num=0,flag=1;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();
    return num*flag;
}
int n,m,bit[M];db ans,p[20];
signed main()
{
	while(~scanf("%d",&n))
	{
		ans=0;m=1<<n;
		for(int i=0;i<n;i++)
			scanf("%lf",&p[i]);
		for(int i=1;i<m;i++)
			bit[i]=bit[i>>1]+(i&1);
		for(int i=1;i<m;i++)
		{
			db s=0;int f=(bit[i]&1)?1:-1;
			for(int j=0;j<n;j++)
				if((1<<j)&i) s+=p[j];
			ans=(ans+f*(1/s));
		}
		printf("%lfn",ans);
	}
}

按位或

https://blog.csdn.net/C202044zxy/article/details/106734521

wait

https://blog.csdn.net/C202044zxy/article/details/97758036

总结

发现很多关于首次达到某个条件的时间（期望次数）的题都可以用$\mathtt{m}\mathtt{i}\mathtt{n}-\mathtt{m}\mathtt{a}\mathtt{x}$反演做，重要的是把时间作为大小比较的关键字来定义出状态，通常最小不好求但是最大好求（或者反之）

最后

以上就是背后星月为你收集整理的[学习笔记] min-max容斥的全部内容，希望文章能够帮你解决[学习笔记] min-max容斥所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。