Min max 容斥
主要应用是在期望里。对于随机变量（通常是时间）构成集合的 min 转化成 max，vice versa。 min 的中文特征：某一。翻译一下就是全集 \(S\) 获得时间最早。 max 的中文特征：全、齐。翻译一下就是全集 \(S\) 获得时间最晚。
与求期望是等价的，因为遍历了所有可能性。
min 转 max 后，某一行填满（全集 \(S\) 获得时间第 \(1\) 早）变成选中的行（列）全填满（穷举 \(T\subseteq S\) 并分配系数，\(T\) 内获得时间第 \(1\) 晚）。 第二个部分是计算 \(T\) 涂满时间的期望。这题允许 \(O(nm)\)，那就直接枚举选中 \(n'\) 行，\(m'\) 列（当然有一些行和列是被始终禁用的，这个处理起来不难。）。这两个数据确定了，要涂的格子数量 \(cnt_{T}\) 就晓得了。 数学事实是（概率-期望的关系来源于后面有提到的几何分布）：
部分抽奖问题 Partial Coupon Collector Problem
对于 \(N\) 个等概率发生的事件，单位时间只能发生一个，如果选中 \(k\) 个，那么这 \(k\) 个全部发生过（也就是最晚的那个发生）的时间期望是 $$ \frac{1}{k/N} + \frac{1}{(k-1)/N} + \cdots+\frac{1}{1/N} $$
max 转 min 后，集齐 k 种（全集 \(S\) 获得时间第 \(k\) 晚）变成得到一种（穷举 \(T\subseteq S\) 并分配系数，\(T\) 内获得时间第 \(1\) 早）。 需要用到 k-th min-max，会多一个二项式系数。这题第二个部分也就是处理一个二项式求和。 数学事实是：
几何分布
对于一个发生概率为 \(p\) 的事件，发生的期望步数为 \(1/p\)。（根据定义求和然后就是高数习题了）。
吐槽
洛谷题解那里说什么初值很神仙、负负得正，其实完全没那必要。前者其实是因为 min-max 容斥特有的不考虑空集，然而我们 initially 手动处理大小为 1 的集合就行了。后者是有点笨了，硬是要把 \((-1)^{k}\) 项和二项式下面的一部分绑定起来，然而这玩意和 sigma 枚举的下标无关，直接提到求和号外面就好了。 经过测试本题实质上没有 \(p=0\) 的数据。如果有的话已有数据约束其实并不够。
从式子推导来说简直是上个问题的弱化版。但是上个问题跑了背包就得 \(O(nm)\) 了，这题过不去。这里其实也就是优化一下这个背包，把系数放进 generating function，跑多项式乘法，然后再统计答案。 当然这里还有一个类似启发式合并的 trick。多项式乘法允许我们在 \((siz_1+siz_2)\log(siz_1+siz_2)\) 合并两个背包，现在要合理安排合并顺序：即采用一个 priority_queue 维护目前最小的两个背包将它们合并。 区别于经典的启发式合并的每一步扩大一倍，即，只有小量产生贡献而每次贡献完规模至少扩大一倍。这里的分析方式是考虑一个对象合并的遗传链，并把两步合成，看作一组。容易发现，一组合并能使规模至少扩大一倍。即这里大量也产生贡献，但是它也能保证每两步扩大一倍。 这里顺便可以复习一下 NTT。为什么要选原根去取代 FFT 的单位根呢？因为要避免 DFT 时重复代入相同的点值，这会导致 DFT 矩阵出现完全相同的两行，从而不满秩，不可逆，无法保证 IDFT 的正确性。
#2542. 「PKUWC2018」随机游走 - 题目 - LibreOJ
可以 max 转 min，也可以不转直接做，主要是因为这题的数学部分中，不像前面那几题把 \(T\) 划分成几类。不同的 \(T\) 其实没啥共同特征，只能穷举后从头模拟。
min 版本
max 版本
很多这种树形期望题都是一个套路。先是写出一堆线性方程组，然后发现 Gauss 消元太菜，然后说树形是特殊情况，有优化解法。 Problem - 5094 hdoj
一定有唯一解
这个优化解法还能借来证明，这样导出的的线性方程组一定有唯一解。 根据树形dp所蕴含的手法，只提取一阶信息（即离某点距离为 \(1\) 的点的信息），结合期望给出的数学等式，可以写出非特殊点 \(i\) 的关系式
其中 \(j\) 枚举 \(i\) 的所有一阶儿子，\(p_i\) 是 \(i\) 的一阶父亲，已经递归说明其所有一阶儿子可以写成一个依赖于 \(f(i)\) 的待定式 \(A_{j}+B_j\cdot f(i)\)。 如果能证明 \(\deg_i - \sum B_{j}\) 不为 \(0\)，那么递归就成立了。这能成立关键在于特殊点的存在。以转成 min 为例，特殊点 \(i'\) 是存在于 \(T\) 的点。它们的 \(f(i')=0\)，形式上可以写成 \(A_{i'}+B_{i'}\cdot f(p_{i'})\)，只不过两个系数都是 \(0\) 而已。min max 不考虑空集，所以必有特殊点。
对于非特殊叶子结点 \(j\)，的确有 \(B_{j}=1\)，导致往上传递出去的 \(B_{p_j}\) 会是
$$ \frac{1}{(\deg_{p_{j}} - \sum B_j )} $$ 如果所有 \(B_j\) 都递归地是 \(1\)，考虑到 \(\deg_{p_j}\) 大多数都是一阶儿子数量 + 一阶父亲数量，会发现 \(B_{p_j}\) 也得是 \(1\)。于是到了根节点，boom，没父亲了，\(\deg\) 等于一阶儿子数量了，分母成 \(0\) 了。 然而特殊点的存在，能扭转这个尴尬情况。具体地说，由于在某个点转折了，\(B_i\) 因为特殊点变小成 \(0\) 了，考虑道上面这个式子关于 \(B\) 的变大变小是同步的，于是传递上去的 \(B\) 就变小了。于是跑到根节点时，要么根节点也是特殊点不用管这个式子，要么就是一阶儿子有一些被特殊点影响到而把 \(B\) 变小了，于是 \(\sum B\) 比 \(\deg\) 小了。
另外复习子集前缀和（俗称 SOSDP）可以看这篇，比较直观 https://www.cnblogs.com/maple276/p/17975253
一道可以转化成子集前缀和问题的题目。 D - Prefix XORs 其中另外两个部分是：计算多次前缀和操作后，某一位对最后一位的贡献，这个部分的答案是一个组合数求和；第二个部分是考虑到不进位加法可以把系数在 mod2 意义下考虑，应用 lucas 定理把组合数转换成一个 inverson 符号（或者说 bool 表达式）。再稍作转化发现可以最终转化成子集前缀和问题。