题解：P4704 太极剑

· · 题解

拓展 Min-Max 容斥。如下：

\max_k(S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)

其中

\max\limits_k(S)

表示

S

中第

k

大的值。这个式子与 Min-Max 容斥的区别在于容斥系数。我们来证明一下。

因为系数只与

T |

有关，所以设

i

为

=i

时的系数。对于

S

中第

i

大的值，会被算

\sum\limits_{j=1}^{i-1}\binom{i-1}{j}f_{j+1}

次。则

$f_ i

都仅剩一项，即得

然后就是一个简单的 DP。不多说。