Min-Max 容斥

Min-Max 容斥算法

Min-Max 容斥可以在已知一者的情况下求出另外一者，如

\max(a,b)=a+b-\min(a,b)\\ \max(a,b,c)=a+b+c-\min(a,b)-\min(a,c)-\min(b,c)+\min(a,b,c)

我们把这个式子推广到 $n$ 个变量的情况的话，就有（令 $S=\set{a_1,a_2,\dots,a_n}$ ）

\min(S)=\sum_{T\subseteq S} (-1)^{|T|-1} \max(T)\\ \max(S)=\sum_{T\subseteq S} (-1)^{|T|-1} \min(T)

扩展：

k

-th Min-Max 容斥

\mathop{\mathrm{min_k}}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max(T)\\\mathop{\mathrm{max_k}}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)

证明