P15653 题解

zjy2008 · 2026-03-09 23:19:58 · 题解

我的哈集幂怎么变成大构交了。

首先考虑一些简单的不变性，k\bmod 2 = 1 时每个点的度数奇偶性不变，\dfrac{k(k-1)}{2}\bmod 2 = 1 时边数的奇偶性不变。在满足以上两点之后，我们声称所有可能的图都是可达的。记一开始的图与最终的图的对称差为 G，这是容易计算的。记 G_{u,v}=1 当且仅当 (u,v) \in G。

首先考虑 n=k+2 的情形。假设不包含 u 的操作次数为 d_u，同时不包含 u,v 的操作次数为 d_{u,v}，总操作次数为 S，那么 (u,v) 存在当且仅当 S-d_u-d_v+d_{u,v} \equiv 1\pmod 2。所以我们有 d_{u,v} \equiv G_{u,v}+d_u+d_v+S\pmod 2,(n-1)d_u \equiv \sum G_{u,v}\pmod 2,(\dfrac{n(n-1)}{2}+1)S \equiv \sum G_{u,v}\pmod 2,\sum d_u \equiv0 \pmod 2，并且只需要它的任意一组解即可。于是直接取 S \equiv \sum G_{u,v} \pmod 2,d_u \equiv \sum G_{u,v}\pmod 2 就可以解出一组合法的 d_{u,v} 的解。

若 n>k+2，我们做归纳法，不断操作直到与 n 相关的边满足限制，然后把做 n-1 大小的子问题。若不满足的边 \ge k-1，直接异或上这 k-1 条边；否则若不满足的边数为偶数，假设两条边是 (u,n),(v,n)，操作 \{n,u,S\},\{n,v,S\}；否则操作一次包含所有不满足的边的集合，然后做不满足的边数为偶数的情形。可以证明这样的操作次数不超过 \dfrac{n-1}{k-1}+k-2\le n-1。

综上我们可以做到 O(nk^2+n^2) 的时间复杂度。