![[学习笔记] min-max容斥](/uploads/reation/bcimg1.png)
[学习笔记] min-max容斥
结论及证明给定集合SSS，max(S)max(S)max(S)为集合SSS中的最大值，min(S)min(S)min(S)为集合SSS中的最小值，则我们有一个式子：max(S)=∑T⊆S(−1)∣T∣−1×min(T)max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}\times min(T)max(S)=T⊆S∑(−1)∣T∣−1×min(T)不多说，直接开证（淦 ），首先我们设一个容斥系数f(∣T∣)f(|T|)f(∣T∣)使这个式子成立：max(S)=∑T⊆Sf
