题解：AT_xmascon22_f Fast as Fast as Ryser

SegTree · 2025-12-10 11:20:45 · 题解

不妨令 n 为偶数。若在 2i 与 2i+1 之间连边，则图由若干环和链构成，且 \dfrac{n}{2} 减去链的个数为匹配个数。

考虑如何让环和链的情形都不重不漏。考虑取当前集合内的 p=\text{mex} 来扩展集合。则环的情形为 p\to \cdots \to p+1，链的情形为 a\to \cdots\to p\to p+1\to \cdots \to b。

设 f_{s,i,0/1} 表示当前经过了集合 s 内的点，从 p 或 p+1 开头的链的权值和；g_{s,i} 表示共计 i 条链，使用的点集为 s。转移是简单的。

对于每个 i，s 一定包含 0\sim i-1 中的点，因此时间复杂度为 O(2^nn^2)。

https://atcoder.jp/contests/xmascon22/submissions/71596509。