最近的做题记录比较鸽，随便发了一个之前的听课记录出来。
主要是过年比较摆吧……争取几天后恢复更新。
回顾 P8340 [AHOI2022] 山河重整，发现互异分拆可以得到一个与普通分拆数类似的观察方向。
我们考察互异分拆的 Ferrers 图中一条从右上角起始，下步右步交替的格路，其围出的部分与整数分拆中的 Durfee square 很类似。
去除 \(h\times h\) 的 Durfee square 后，两侧放置的均为 \(\leqslant h\) 的整数分拆，因此我们立即得到：
\[\prod_{k\geqslant 1}\frac{1}{1-x^k}=\sum_{h\geqslant 0}x^{h^2}(\prod_{k=1}^h\frac{1}{1-x^k})^2 \]同理，去除这样一个结构后，下方剩余的为 \(\leqslant h\) 的整数分拆，那么就能得到：
\[\prod_{k\geqslant 1}(1+x^k)=\sum_{h\geqslant 0}x^{\frac{h(h+1)}2}\prod_{k=1}^h\frac{1}{1-x^k} \]这些形式很容易让人联想到与分拆数关系紧密的五边形数定理，不过我并不清楚其中是否存在联系！
\[\prod_{k\geqslant 1}(1-x^k)=\sum_{k\geqslant 0}(-1)^kx^{\frac{k(3k\pm 1)}{2}} \]读 gyr 的论文过程中遇到了一个这样的问题：构造 \(n\) 阶 Hypercube 的最小链覆盖。
根据 Dilworth 定理，最小链覆盖的值等于最长反链，而 Sperner 定理告诉我们，最长反链为 popcount 等于 \(\lfloor\frac n2\rfloor\) 的所有点。
通过构造 Hypercube 相邻层之间关于点数较少一侧的完美匹配，我们很容易得到最小链覆盖的方案。
下面说明完美匹配一定存在，并给出一个复杂度优于朴素 Dinic 的做法。（其实我也没有分析朴素 Dinic 在这样的图的复杂度，所以纯纯口胡！）
假设左部点点数较少，左部有 \(n\) 个点，每个点度数为 \(d_l\)；右部 \(m\) 个点，每个点度数为 \(d_r\)，那么 \(nd_l=md_r\)，因此 \(d_l\geqslant d_r\)。
完美匹配的存在性比较好说明，使用 Hall 定理，我们只需证明任意左部点子集 \(S\) 都满足 \(|S|\leqslant|N(S)|\)。
连接 \(S\) 的边数量为 \(|S|d_l\)，而连接 \(N(S)\) 的边数量为 \(|N(S)|d_r\)，前者是后者的子集，因此有 \(|S|d_l\leqslant |N(S)|d_r\)，即 \(|S|\leqslant|N(S)|\)。
我们尝试通过补点的方式，使其两侧点数相等，每个点度数相等。
我们给左部补上 \(m-n\) 个点度数等于 \(d_l\) 的点，每次加入一个点都选择右部度数最小的 \(d_l\) 个点与其连边，容易发现右部每个点度数最终都会恰好为 \(d_l\)。
构造这张新图的完美匹配是一个经典问题，Hall 定理；正则二分图的完美匹配 有较为详细的算法流程。
简要概括一下，我们每次随机选择一个左部未匹配点，随机遍历二分图寻找增广路，复杂度期望下为 \(O(n\log n+m)\)。
标签：度数,frac,28,geqslant,分拆,2023,29.5,prod,leqslant From： https://www.cnblogs.com/xiaoziyao/p/17071289.html