min-max 容斥学习笔记

假设要求一个集合 |S| 的最大值，可以利用 |S| 子集的最小值容斥求出。

\max(S)=\sum_{T\in S}(-1)^{|T|+1}\min(T)

可以扩展到第 k 大。

kth\max(S)=\sum_{T\in S}(-1)^{|T|+k} \binom{|T|-1}{k-1} \min(T)

同理，可以用最大值容斥出最小值。

比较神奇的是这个式子在期望意义下依然成立。

E(\max(S))=\sum_{T\in S}(-1)^{|T|+1}E(\min(T))

对于一个子集 T ，求 E(\min(T)) 是容易的，为 \frac{\sum p}{\sum\limits_{u\in T}p_u} ，其实就是概率倒数。

题目求的是前 k 小，但是我们 \min 只能容斥出 \max ，所以令 k=n-k+1 ，相当于求前 k 大，且 1\le k\le 11 。

考虑把整个式子列出来。

kth\max(S)=\sum_{T\in S}(-1)^{|T|+k}\binom{|T|-1}{k-1}\frac{\sum p}{\sum_{u\in T}p_u}

发现 m\le 10000 ，所以将 \sum_{u\in T}p_u 压入状态。

令 f_{i,j,k} 表示考虑了前 i 个数，|T|=j，\sum\limits_{u\in T}p_u=k 的方案数，转移和统计是简单的。

复杂度 O(n^2m) ，可以有 70 pts 。

考虑优化。

每个数肯定要一次次枚举的，然后 \sum_{u\in T}p_u 感觉很难优化掉，所以考虑能不能通过一些性质把 j 优化掉。

考虑和 j 有关的两项。

对于 (-1)^{|T|+k} ，发现每次都是从 j-1 向 j 转移，所以我们不妨直接将这一项计入 dp 值，每次转移从加变成减即可。

对于 \binom{|T|-1}{k-1} ，我们发现这玩意似乎非常难优化，但是 k\le 11 ，或许能往这上面想。

考虑杨辉三角的式子 \binom{|T|-1}{k-1}=\binom{|T|-2}{k-1}+\binom{|T|-2}{k-2} ，而下面的 k-1,k-2 又非常小，这启发我们根据 \binom{m}{n} 的 n 去设计状态。

令 f_{i,j,k} 表示考虑前 i 个数，\sum\limits_{u\in T}p_u=k ，方案数乘上 (-1)^{|T|+k}\binom{|T|-1}{j-1} 的值。

转移时考虑 f_{i,j,k} 从 f_{i-1,j,k-p_i} 和 f_{i-1,j-1,k-p_i} 转移即可。

复杂度 O(nmk) 。

考虑怎么求一个子集 T 的 E(\min(T)) 。

考虑子集内有一个数被选了 b_k-1 次，然后其他数都被选了 c_i(c_i<b_i) 次，最后再选一次 k 。那么这个 k 就是第一个被选的数。

令 S_a=\sum a,s_a=\sum\limits_{u\in T}a_u,s_c=\sum\limits_{u\in T}c_u ，这里令 c_k=b_k-1 。

选中一次 T 内的数的期望次数为 \frac{S_a}{s_a} 。

那么 T 贡献的式子为：

(-1)^{|T|+1}(s_c+1)\frac{S_a}{s_a}\frac{s_c!}{\prod_{i\in T}c_i!}(\frac{a_k}{s_a})^{b_k}\prod_{i\in T,i\neq k}(\frac{a_i}{s_a})^{c_i}

直接把 s_a,s_c 压入状态即可，(-1)^{|T|+1} 的处理类似上题。

具体地，令 f_{i,j,k,0/1} 表示考虑了前 i 个数，s_a=j ， s_c=k ，且是否选好了第一个被选的数时的 dp 值。

转移时暴力枚举状态，然后枚举 c_i ，看似复杂度是 O(n\sum a(\sum b)^2) ，但实际复杂度为 O(\sum a(\sum b)^2) ，复杂度证明参考树上背包。

https://atcoder.jp/contests/agc038/submissions/32809044