前置知识
请牢记二项式定理：
\((a+b)^n = \sum\limits_{i=0}^{n}{\dbinom{n}{i}a^{n-i}b^i}\)
或另外一种形式：
\((a+1)^n = \sum\limits_{i=0}^{n}{\dbinom{n}{i}a^{n-i}}\)
min-max 容斥
min-max 容斥的主要思想是给每个子集分配一个系数（然后每个属于子集的 \(a_i\) 的系数加上该系数），使得 \(S\) 的最大值 \(a_i\) 的系数为 \(1\)，其余为 \(0\)。
问：一个集合 \(S\)，每次可以询问一个子集的 min 值，如何求 \(S\) 的 max 值？
\(S\) 的 max 等于 \(\sum\limits_{T\subseteq S}{(-1)^{|T| - 1}min(T)}\)。
证明：
- 假设 \(S\) 是从大到小排序的，长度为 \(n\)。
- 那么 \(T\subseteq S\) 满足 \(min(T) = a_k\) 的系数之和（\((-1)^{|T| - 1}\)）是多少？
- 是 \(\sum_{l = 0}^{k - 1}{\dbinom{k-1}{l}(-1)^{l}}\)
- 注意到这就是二项式定理，等于 \((-1+1)^{k-1}\)，即 \(0^{k-1}\)
- 显然只有当 \(k = 1\) 的时候（即最大值）系数之和为 \(1\)，其他都是 \(0\)。