min-max容斥及其拓展

求解集合中的最大值和最小值以及$k-th$大值和$k-th$小值

证明

直接证明$k-th$小值的式子吧

min ⁡ k { S } = ∑ T ⊆ S ( − 1 ) ∣ T ∣ − k C ∣ T ∣ − 1 k − 1 max ⁡ { T } min_k{S}=sum_{Tsubseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}max{T} kmin​{S}=T⊆S∑​(−1)∣T∣−kC∣T∣−1k−1​max{T}

证明

设没有重复的数，如果有的话可以通过加上$esp$来解决

要构造一个$f$，满足 min ⁡ k { S } = ∑ T ⊆ S f ( ∣ T ∣ ) max ⁡ { T } min_k{S}=sum_{Tsubseteq S}f(|T|)max{T} mink​{S}=∑T⊆S​f(∣T∣)max{T}

考虑每个值的贡献。设他从小到大的排名为$x$

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

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

$$F(i)=f(i+1)$$

然后二项式反演

$$g(qwq)=\sum _{i=0}^{qwq}{C}_{qwq}^{i}F(i)$$

$$F(qwq)=\sum _{i=0}^{qwq}(-1{)}^{qwq-i}{C}_{qwq}^{i}g(i)$$

$$f(qwq+1)=\sum _{i=0}^{qwq}(-1{)}^{qwq-i}{C}_{qwq}^i[i=k-1]$$

$$f(qwq+1)=(-1{)}^{qwq-k+1}{C}_{qwq}^{k-1}$$

$$f(qwq)=(-1{)}^{qwq-k}{C}_{qwq-1}^{k-1}$$

最后

以上就是潇洒小天鹅为你收集整理的min-max容斥及其拓展的全部内容，希望文章能够帮你解决min-max容斥及其拓展所遇到的程序开发问题。

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