https://www.lydsy.com/JudgeOnline/problem.php?id=2891
Hall定理：
设一个二分图的两边分别为 U,V U , V ，对于点集 S∈U S ∈ U ，记录 adj(S) a d j ( S ) 为与 S S 直接有边相连的点（邻集），显然adj(S)∈Vadj(S)∈V。
一个二分图 U,V U , V 有完备匹配的充要条件是：对于任意一个 S∈U S ∈ U ， |adj(S)|≥|S| | a d j ( S ) | ≥ | S | 。
令题目描述中点的数量为 a a 的那边为UU， b b 为VV。
定义Hall集合为满足上述条件的点集，所有的Hall集合的集合为HS集。显然，所有Hall集合都 ∈U ∈ U 。
将所有HS集合对应到一个unsigned long long上面，第 k k 位为11代表HS集合中有二进制状态为 k k 的Hall集合。
由于Hall定理，HS集合的个数不会超过40004000，因此可以用Hash/map映射到一个int上面。
设 fi,j f i , j 代表 V V 集合中已经选择了[1,i][1,i]这些点， U U 中HS集合在Hash/map中对应的int为jj，造成这种情况的概率为 fi,j f i , j 。
如果我们能够求出 fi,j f i , j ，那么最终的答案就是 ∑fb,HS×Max(HS) ∑ f b , H S × M a x ( H S ) ，其中 Max(HS) M a x ( H S ) 代表 HS H S 中最大的集合个数。
那么如何求 fi,j f i , j ？显然， f0,∅=1 f 0 , ∅ = 1 。
考虑 j j 状态能够转移得到的状态，令gj,kgj,k为：如果当前的HS为 j j ，新加入的点的邻点为kk（ k k 为nn个点的二进制状态），那么两个加起来的HS为 gj,k g j , k （ j,gj,k j , g j , k 为HS的二进制状态对应Hash/map中的int），那么显然有转移： fi,gj,k=fi−1,j+P(i,k) f i , g j , k = f i − 1 , j + P ( i , k ) （其中 P(i,k) P ( i , k ) 为 i i 点的邻点的二进制状态为kk的概率）。
考虑如何求出 gj,k g j , k 。分情况讨论：
如果 k k 只有一个点，不妨设这个点的编号为xx。
那么现在的集合中是HS集合的情况有两种：
原来就属于HS集合的集合。
加入了这个点 x x 而变成了HS集合的集合。
显然，这种集合满足|adj(S)|=|S||adj(S)|=|S|。经过理性分析可以得到：要满足上述条件，原HS集合必须包含 S−{x} S − { x } 这个集合。
因此， gj,k=j+{S∣{x}∈j&(S−{x})∈j} g j , k = j + { S ∣ { x } ∈ j & ( S − { x } ) ∈ j } 。其中， & & 表示条件之间的与（C++中的 && & & ）。
如果 k k 有多个点。
按上面的思路进行分析，显然可以得到：gj,k=j {S∣x∈k&{x}∈S&(S−{x})∈j}gj,k=j {S∣x∈k&{x}∈S&(S−{x})∈j}，其中 & & 的意义同上。
那么我们就可以求出 g g 数组了，由于求出的gg数组中的元素都是合法的HS集合，因此可以边求 g g 数组边将HS映射到Hash/map中。
时间复杂度：
求gg数组： 第一维 O(HS(n)) O ( H S ( n ) ) 第二维 O(2n) O ( 2 n ) 转移 O(n) O ( n ) 求 f f 数组： 第一维O(m)O(m)第二维 O(HS(n)) O ( H S ( n ) ) 转移 O(2n) O ( 2 n )总时间复杂度： O((n+m)×HS(n)×2n) O ( ( n + m ) × H S ( n ) × 2 n ) ，其中 HS(n) H S ( n ) 代表HS集合中每个元素大小不超过 n n <script type="math/tex" id="MathJax-Element-67">n</script>的集合种类数。
