容斥极值公式是指在一些集合的交集中选取一定数量的元素，使得这些元素的某个函数取得最大或最小值的公式。其推导过程如下：
假设有 $n$ 个集合 $A_1,A_2,cdots,A_n$，它们的交集为 $S=A_1cap A_2capcdotscap A_n$，设 $f(x)$ 是 $S$ 中元素 $x$ 的某个函数。我们要从 $S$ 中选取 $k$ 个元素，使得它们的函数值之和最大。
我们用 $f_i(x)$ 表示 $x$ 在 $A_i$ 中的函数值，显然有 $f(x)=sum_{i=1}^n f_i(x)$。我们记 $S_k$ 为 $S$ 中选取 $k$ 个元素的集合，$f(S_k)$ 表示 $S_k$ 中所有元素的函数值之和。于是我们要求的是：
$$max_{S_ksubseteq S,|S_k|=k} f(S_k)$$
我们可以通过容斥原理来解决这个问题。首先我们求出所有 $A_i$ 的并集 $T=A_1cup A_2cupcdotscup A_n$，并将 $T$ 中的元素按照在哪些集合中出现过分成 $n+1$ 组：
$$T_0=Tsetminus S,T_i=A_isetminus S,(1leq ileq n)$$
显然 $T_0$ 中的元素均不在 $S$ 中，而 $T_i$ 中的元素都在 $S$ 中但不在 $A_i$ 中。于是我们可以得到：
$$S_k=bigcup_{i=1}^k (Scap T_i),quad(0leq kleq n)$$
这是因为要选 $k$ 个元素，就必须从 $k$ 个集合中至少选出一个元素，而这个元素就可以来自 $T_i$ 中的任意一个元素。
接下来我们考虑 $f(S_k)$ 的值。显然有：
$$f(S_k)=sum_{i=1}^nsum_{xin Scap T_i}f_i(x)$$
我们可以将 $x$ 的求和范围拆分成若干个集合的交，并利用容斥原理来求解。例如，当 $k=2$ 时，我们有：
$$begin{aligned} f(S_2)&=sum_{i=1}^nsum_{x,yin Scap T_i,x
eq y}f_i(x)+sum_{i<j}sum_{xin Scap T_i,yin Scap T_j}f_i(x)+f_j(y) &;;;;-sum_{i=1}^nsum_{xin Scap T_i}sum_{yin Scap T_i,y
eq x}f_i(x)-sum_{i<j}sum_{xin Scap T_i,yin Scap T_j}sum_{zin Scap T_i}sum_{win Scap T_j,w
eq y}f_i(z)+f_j(w) &=sum_{i=1}^nsum_{x,yin Scap T_i,x
eq y}f_i(x)+sum_{i<j}sum_{xin Scap T_i,yin Scap T_j}f_i(x)+f_j(y) &;;;;-sum_{i=1}^nsum_{x,yin Scap T_i,x<y}f_i(x)-sum_{i<j}sum_{xin Scap T_i,yin Scap T_j}f_i(x)-f_j(y)end{aligned}$$
我们可以发现，其中的第一行是在求集合的并，而第二行是在求集合的交。根据容斥原理，这两行的差值即为 $f(S_2)$ 的值：
$$f(S_2)=sum_{i=1}^nsum_{x,yin Scap T_i,x<y}f_i(x)-sum_{i<j}sum_{xin Scap T_i,yin Scap T_j}f_i(x)-f_j(y)$$
我们可以类似地求得 $f(S_k)$ 的值，从而得到 $max_{S_ksubseteq S,|S_k|=k} f(S_k)$ 的值。最终答案即为 $max_{k=0}^nmax_{S_ksubseteq S,|S_k|=k} f(S_k)$。
