由于准备补数学，所以准备找个垃圾桶把令人无法理解的有意义内容记一下。

Min-Max 容斥

找到了一个非常好证明，考虑 从大到小排序之后是 ，那么显然左边是 ，接下来证明右边是 ：

考虑对于 的值分讨贡献：

• ：此时右边是 。
• ：此时 包含 中的任意个与一个 ，那么总的集合数量为 个，由单位根反演得其中大小为奇数与偶数的均为 个，所以总和为 。

以上证明 对换，然后从小到大排序得到：

扩展 Min-Max 容斥

不会。

HAOI2015 按位或

显然把最大值转成最小值，然后考虑集合怎么整，由于我们求的是 ，所以集合里只要选上一个，于是考虑算所有与当前集合 有交集的集合 的概率总和。但是这并不好算，考虑反过来求没有交集的 的概率。这些 满足是 的子集，那么得到一个卷积的柿子： 用 FWT 算出 ，然后套进 Min-Max 容斥的柿子里： 使用了经典结论 概率成立的事件期望成立次数为 。