作用：
把一个集合的最小值转换成任意k大值，或者把最大值转换成任意k小值。
基本形式：
[min(mathbb S) = sum limits_{emptyset
eq mathbb T subseteq mathbb S} (-1)^{|mathbb T|+1} max(mathbb T), max(mathbb S) = sum limits_{emptyset
eq mathbb T subseteq mathbb S} (-1)^{|mathbb T|+1} min(mathbb T)
]
证明：（以第一个式子为例）
设(min(mathbb S) = sum limits_{emptyset eq mathbb T subseteq mathbb S} f(|mathbb T|) max(mathbb T),)
则我们思考第(k+1)小的数在右式中的贡献，只有在集合(mathbb T)中的数全部为比第(k+1)小的数还小的时候才会有，由此我们可以得到贡献为(sum limits_{i=0}^{k} C_k^i cdot f(i+1))。
我们令(F(x) = f(x+1), G(x) = [x==0])，则(G(k) = sum limits_{i=0}^{k} C_k^i cdot F(i))。
对该式子进行二项式反演，则(F(k) = sumlimits_{i=0}^k (-1)^{k-i}C_k^i G(i))
所以(f(x) = (-1)^{(k-i)} = (-1)^{(|mathbb T+1|)})
同理，反之亦然。
扩展
min_max容斥更普遍的情况：
[kthmin(mathbb S) = sum limits_{emptyset
eq mathbb T subseteq mathbb S} (-1)^{|mathbb T|-k}C_{|mathbb T|-1}^{k-1} kthmax(mathbb T), kthmax(mathbb S) = sum limits_{emptyset
eq mathbb T subseteq mathbb S} (-1)^{|mathbb T|-k}C_{|mathbb T|-1}^{k-1} kthmin(mathbb T)
]
证明方法和上面的方法相似，都是用二项式反演倒腾一下。
此外，这个式子在期望意义下也成立（然而不会证），即：
[E(kthmin(mathbb S)) = sum limits_{emptyset
eq mathbb T subseteq mathbb S} (-1)^{|mathbb T|-k}C_{|mathbb T|-1}^{k-1} E(max(mathbb T))
]
例题 （HDU 4336）Card Collector
十分的裸，可以直接带到上面的式子。(n)也足够小
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
namespace ztd{
using namespace std;
typedef long long ll;
template<typename T> inline T read(T& t) {//fast read
t=0;short f=1;char ch=getchar();double d = 0.1;
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') t=t*10+ch-'0',ch=getchar();
if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
t*=f; return t;
}
}
using namespace ztd;
const double eps = 1e-6;
const int maxn = 22;
int n, m;
double a[maxn], ans;
void dfs(int x, double p, double sign){
if(x == n+1){
if(p > eps) ans += (double)(sign/p);
return;
}
dfs(x+1, p, sign); dfs(x+1, p+a[x], -sign);
}
inline void Main(){
ans = 0;
for(int i = 1; i <= n; ++i) read(a[i]);
dfs(1, 0, -1);
printf("%.6f
", ans);
}
signed main(){
while(scanf("%d", &n) != EOF) Main();
return 0;
}