关于用一个集合的子集的 min 求这个集合的 max 的问题。当然用 max 求 min 也可以。
考虑构造一个只和集合元素个数有关的 ( f( left | S ight | ) ) ，使得可以
( kthmax(S)=sumlimits_{T subseteq S} f( left | T ight | ) min(T) )
考虑第 i 大的元素被计算了几次，就是 ( sumlimits_{j=0}^{i-1}C_{i-1}^{j}f(j+1) )
第 i 大的元素作为 min(T) 出现，说明其它元素都是比它大的。
需要 ( sumlimits_{j=0}^{i-1}C_{i-1}^{j}f(j+1) = [i=k] )
让 i 表示 i-1 ( sumlimits_{j=0}^{i}C_{i}^{j}f(j+1) = [i=k-1] )
令 ( g(i)=[i=k-1] , h(i)=f(i+1) )
则 ( sumlimits_{j=0}^{i}C_{i}^{j}h(j)=g(i) )
二项式反演 ( h(i) = sumlimits_{j=0}^{i}(-1)^{i-j}C_{i}^{j}g(j) )
当 ( j=k-1 ) 时 ( g(j) ) 不为 0 ，所以 ( h(i)=(-1)^{i-k+1}C_{i}^{k-1} )
即 ( f(i) = (-1)^{i-k}C_{i-1}^{k-1} )
求第 k 大的话，只要统计元素个数 >=k 的集合即可。
思考：用 gcd(S) 表示 lcm(S) ？
设有 cnt 个质因子。( p_{i} ) 表示第 i 个质因子， ( t_{ji} ) 表示第 j 个元素的第 i 个质因子的指数。
( lcm(S)=prodlimits_{i=1}^{cnt}p_{i}^{ maxlimits_{_{j in S}} {t_{_{ji}}} } )
( gcd(S)=prodlimits_{i=1}^{cnt}p_{i}^{ minlimits_{_{j in S}} {t_{_{ji}}} } )
( lcm(S)=prodlimits_{i=1}^{cnt}p_{i}^{ sumlimits_{_{T subseteq S}}(-1)^{^{left | T ight | -1}} minlimits_{_{j in T}} {t_{_{ji}}} } )
指数上的 ( sum ) 就是底数上的 ( prod ) ，所以
( lcm(S)=prodlimits_{T subseteq S}gcd(T)^{ (-1)^{left | T ight | -1} } )