Marek and Matching (hard version)
非常好 trick，我又没见过。搬运写一下题解。
二分图完美匹配直接考虑 Hall 定理，Hall 定理的内容要求 \(\forall S,|S|\le |N(S)|\)，这个 \(\forall\) 非常不好，于是正难则反，计算不合法方案，但是这个不合法方案看着就很容易算重，然后你如果去考虑用 \(ans=\sum (-1)^res(i)\)（\(res(i)\) 表示有 \(i\) 个 \(S\) 满足 \(|S|>|N(S)|\) 的概率）计算答案基本就废了，这题我们要考虑换一个思路。
我们考虑对每一个不合法情况（也就是没有完美匹配）钦定一个代表元，这题中我们钦定 \(|S|-|N(S)|\) 最大的 \((S,N(S))\) 为代表元（相同取 \(|S|\) 小的），下面我们证明对于一个不合法情况，代表元 \(S\) 是唯一确定的。
假设同时存在最优的 \(S,T\)，\(|S|-|N(S)|=|T|-|N(T)|,|S|=|T|,S\ne T\)，那么注意到：
\[\begin{aligned}|S|-|N(S)|+|T|-|N(T)| &= (|S|+|T|)-(N(S)+N(T)) \\&= (|S\cup T|+|S\cap T|)-(|N(S)\cup N(T)|+|N(S)\cap N(T)|) \\&= (|S\cup T|+|S\cap T|)-(|N(S\cup T))|+|N(S)\cap N(T)|) \\&\le (|S\cup T|+|S\cap T|)-(|N(S\cup T))|+|N(S\cap T)|) \\\end{aligned}\]
于是 \(S\cup T,S\cap T\) 中必有一个更优的。
于是我们就可以 DP 了，设 \(f_{S,T}\) 表示 \(S,T\) 之间有完美匹配的概率，\(g_{S,T}\) 表示 \(S,T\) 之间没有完美匹配且 \((S,T)\) 是代表元的概率，\(no_{S,T}\) 表示 \(S,T\) 之间没有边的概率，\(out_{S,T}\) 表示 \(N(S)=T\) 的概率。（以上定义均只考虑 \(S,T\) 之间的边，其他边的概率都不考虑），转移：
\[g_{S,T} = out_{S,T} - \sum_{S'\subseteq S}\sum_{T'\subseteq T} g_{S',T'}f_{S/S',T/T'}no_{S',T/T'}[|S'|-|T'|\ge |S|-|T|] \]
\[f_{S,T} = out_{S,T} - \sum_{S'\subseteq S}\sum_{T'\subseteq T} g_{S',T'}f_{S/S',T/T'}no_{S',T/T'} \]
解释一下 \(g\) 的转移，\(f\) 类似：容斥，减去代表元不是 \((S,T)\) 的概率，\(f_{S/S',T/T'}\) 是因为如果 \(S/S',T/T'\) 之间没有完美匹配，那么 \((S',T')\) 并上 \(S/S',T/T'\) 的代表元会更优，\(no_{S',T/T'}\) 是为了保证 \(N(S')=T'\)。
复杂度 \(O(3^{2n})\)。
[code]#include#define Debug cerr |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
