题解：P15653 [省选联考 2026] 星图 / starmap

· · 题解

设 \binom{S}{2} 为无序对 (x,y) 组成的集合，V = \mathbb F_2^{\binom{S}{2}}，也即 \binom S2 的所有子集。设双线性型

\langle x, y \rangle = |x \cap y| \bmod 2.

题目里的操作事实上是在取 S 的 k 元子集 A，并通过 \binom A2 \subseteq \binom S2 将 \binom A2 当做 V 中的元素。进行多次操作无非是将多个 \binom A2 做异或，所以我们定义线性空间

U_k = \operatorname{span} \left\{ \binom A2 : |A| = k \right\}.

根据基本的线性代数，存在 A_0,A_1,\dots,A_{d-1} 使得 \binom{A_i}2 是 U_k 的一组基，所以对于每一个 U_k 它都至多用到 \dim U_k \le \dim V = \dfrac{n(n-1)}{2} 个 \binom A2。这告诉我们暂时不用考虑次数限制了。

下面我们证明关于 U_k 的几个定理：

定理 1： 当 |S| \ge k + 6 且 k \ge 2 时，U_k = U_{k+4}。

证明. 首先我们证明 U_{k+4} \subseteq U_k。取 |A| = k+4，并取其 6 元子集 B，设 C = A \setminus B。注意到等式

\binom A2 = \sum_{U \in \binom B2} \binom{C \sqcup U}2

（其中：每条 C \times C 的边被计数了 \binom 62 = 15 次；每条 C \times B 的边被计数了 5 次；一个 B \times B 的边被计数了 1 次；因此在 \operatorname{mod} 2 下等式成立）。所以有 \binom A2 \in U_k，进而 U_{k+4} \subseteq U_k。

然后我们证明 U_k \subseteq U_{k+4}。取 |A| = k，并取 S \setminus A 的 6 元子集 B，注意到等式：

\binom A2 = \sum_{U \in \binom B4} \binom{A \sqcup U}2

（其中：每条 A \times A 的边被计数了 \binom 64 = 15 次；每条 A\times B 的边被计数了 \binom 53 = 10 次；每条 B \times B 的边被计数了 \binom 42 = 6 次；因此在 \operatorname{mod} 2 下等式成立）。所以有 \binom A2 \in U_{k+4}，进而 U_k \subseteq U_{k+4}。

综上，U_k = U_{k+4}，证毕。

如果你打表计算了一些简单的 \dim U_k，你会发现它非常接近 \dfrac{n(n-1)}{2}。你可能在赛前接触过：割空间是回路空间的正交补。因此你会考虑 U_k 的正交补

U_k^\perp = \{x \in V : \forall y \in U_k, \langle x, y \rangle = 0\}.

（注意这里的 \langle x, y \rangle = 0 是在 \operatorname{mod} 2 意义下的，意指 x \cap y 是偶数。）

定理 2： 设 |S| \ge 7，则

\begin{aligned} U_2^\perp = 0, \\ U_3^\perp = \{R \times (S\setminus R) : R \subseteq S\}, \\ U_4^\perp = \left\{0, \binom S2\right\}, \\ U_5^\perp = U_3^\perp \oplus U_4^\perp. \end{aligned}

证明. U_2 的生成元是任意的边 uv，自然 U_2 = V，即 U_2^\perp = 0。

对于 U_3，考虑任意一个点 0 \in S，则 x \in U_3^\perp 一定满足 x_{0u} + x_{0v} = x_{uv}（\{0,u,v\} 的正交性），令 R = \{u : x_{0u} = 0\}，则 R \times (S \setminus R) 的意义是取一个 x_{0u} = 0 且 x_{0v} = 1，让 x_{uv} = 1；如果不存在这样的 (u,v)，则 x_{uv} = 0。结合上我们在考虑无向图，就可以得到 U_3^\perp = \{R \times (S\setminus R) : R \subseteq S\}。

对于 U_4，首先可以验证 \binom S2 \in U_4^\perp（内积为 \binom 42 = 6）。现在考虑一个 x \in U_4^\perp，如果 x \ne 0，那么能取一个 x_{ab} = 1。则对任意一个不同于 a,b 的 c,d，根据 \{a,b,c,d\} 的正交性，有

x_{cd} = 1 + x_{ac} + x_{ad} + x_{bc} + x_{bd}.

记 y_c = x_{ac} + x_{bc}，则式子化作 x_{cd} = 1 + y_c + y_d；再引入两个和 a,b,c,d 都不同的点 e,f，则

x_{cd} + x_{ce} + x_{de} = (1 + y_c + y_d) + (1 + y_c + y_e) + (1 + y_d + y_e) = 1.

但是再考虑 \{a,c,d,e\} 的正交性，可以得到

x_{ac} + x_{ad} + x_{ae} = 1,

同理 x_{ac} + x_{ad} + x_{af} = 1，相减，得到 x_{ae} = x_{af}。因此 x_{at} 关于 t 不变；由因为 3x_{ac} = x_{ac} + x_{ad} + x_{ae} = 1，所以 x_{at} = 1 对于一切 t \notin \{a,b\} 成立。在上述论证中交换 a,b，有 x_{bt} = 1 对于一切 t \notin \{a,b\} 成立，因此 y_c = x_{ac} + x_{bc} = 0，也就是 x_{cd} = 1 + y_c + y_d 中，x_{cd} = 1。得证。

对于 U_5，考虑任意一个点 0 \in S，再取与 0 不同的点 a,b,c,d；根据 \{0,a,b,c,d\} 的正交性，

\sum_{i \in \{a,b,c,d\}} x_{0i} + \sum_{(i, j) \in \binom{\{a,b,c,d\}}{2}} x_{ij} = 0.

如果定义 y_{ij} = x_{0i} + x_{0j} + x_{ij}，带入计算得到

\sum_{(i, j) \in \binom{\{a,b,c,d\}}{2}} y_{ij} = 0.

那么 y \in U_4^\perp，也就是 y_{ij} 要么全 0 要么全 1。也就是 x_{0i} + x_{0j} + x_{ij} = c，即 (x_{0i} + c) + (x_{0j} + c) + (x_{ij} + c) = 0，换言之 (x+c) \in U_3^\perp，得到

U_5^\perp \subseteq U_3^\perp \oplus U_4^\perp;

而 \supseteq 是不难计算验证的。

定理 3：

\begin{aligned} U_2 = V; \\ U_3 = \{x : \forall u,\deg(u)\ \text{是偶数}\}; \\ U_4 = \{x : |x|\ \text{是偶数}\}; \\ U_5 = U_3 \cap U_4. \end{aligned}

证明. 根据 A^{\perp \perp} = A 可以得到 U_2,U_4 的情况；关于 U_3，我们来计算 R \times (S\setminus R) 的正交补。取 R = \{v\} 就得到 v \times (S\setminus \{v\})，它与 x 的交的大小恰好就是 \deg_x(v)，而 v \times (S\setminus \{v\}) 正好是 U_3^\perp 的一组基，所以 U_3^{\perp\perp} 恰好就是 \{x : \forall u,\deg(u)\ \text{是偶数}\}。关于 U_5 的断言来源于

(A+B)^\perp = A^\perp \cap B^\perp.

现在来考虑最优化问题：

定理 4： 对于最优化问题，若 q 为图中度为奇数的点的个数，M = \dfrac{n(n-1)}{2}，则

\begin{array}{l|r} k \equiv 2 \pmod 4 & \mathrm{ans} = M. \\\\\\ k \equiv 3 \pmod 4 & \text{ans} = \begin{cases} M - \dfrac q2, & 2 \nmid n; \\ M - \dfrac{n-q}{2}, & 2 \mid n. \end{cases} \\\\\\ k \equiv 4 \pmod 4 & \mathrm{ans} = \begin{cases} M, & 2 \mid (M-m); \\ M - 1, & 2 \nmid (M-m). \end{cases} \\\\\\ k \equiv 5 \pmod 4 & \mathrm{ans} = \begin{cases} M, & d = 0, \sigma = 0; \\ M-3, & d = 0, \sigma = 1; \\ M - \dfrac d2, & d > 0, d \equiv 2 \sigma \pmod 4; \\ M - \dfrac{d+2}{2} & d > 0, d \not{\equiv} 2 \sigma \pmod 4. \end{cases} \\\\ & \text{其中}\ d = \begin{cases} q, & 2 \nmid n; \\ n-q, & 2 \mid n; \end{cases} \\ &\sigma = (M - m) \pmod 2. \end{array}

证明. 根据定理 3 的刻画，k \equiv 2 \pmod 4 的情况是平凡的；

对于 k \equiv 3 \pmod 4 的情况，我们要找一个 C \in V，使得 G + C 有最多的边且 C 的所有点度数都是偶数；对 H = G+C，我们就要 H 有最多的边且 H+G 的所有点度数都是偶数。也就是，H 的补图，K = H + \binom S2 有最少的边且 K + \binom S2 + G 所有点度数都是偶数，也就是说 K 的所有点的度数的奇偶性都确定。根据图论基本恒等式

2m = \sum_{u \in S} \deg_K(u),

所以只需要让 \deg_K(u) 相应地取 \{0,1\} 就好了。不难计算得到公式。

对于 k \equiv 4 \pmod 4 的情况，你可以在不改变 m 的奇偶性的前提下任意修改图。

对于 k \equiv 5 \pmod 4 的情况，按照 3 的情况考虑 K = G+C+\binom S2，那么还需要要求 m 的奇偶性相应地确定。如果我们需要补边以翻转奇偶性：做 K \gets K + \binom{\{u,v,x\}}{2}。如果存在 \deg_K(u) = \deg_K(v) = 1，那么这样的 K 比原来多了 1 条边，否则是 3 条。不难计算得到公式。

按照上面的证明应该不难构造出目标图 G'。现在我们来考虑一条从 G 到 G' 的路径，也就是从空到 G+G' 的路径。

考虑预留后 k 个位置：n-k,n-k+1,\dots,n-1（点从 0 开始编号）。

定理 5： 可以在 \mathrm O(n^3) 的时间内，构造一组方案，从 0 到达 G+G'。

定理 5 (a)： 对于每一个图 H，若已知 H \in U_k，则有简单的算法，在 \binom{n-k}{2} 次操作内，得到一个图 H'，使得它不存在满足 0 \le i < j < n-k 的边 ij。

证明. 对于任意一条边 0 \le i < j < n-k，使用团 E = \{i,j,n-k,n-k+1,\dots,n-3\}，则可以清除边 ij 的同时，不影响其他的 0 \le p < q < n-k 的 pq。由于至多存在 \binom{n-k}{2} 条 ij 边，所以至多需要这些操作。

定理 5 (b)： 对于每一个图 H'，若已知 H' \in U_k，且它中不存在满足 0 \le i < j < n-k 的边 ij，则存在简单的算法，在 k(n-k) 次操作内，得到一个新图 H''，使得不存在满足 0 \le i < n-k 的 ij。

证明. 考虑扫一遍 0 \le i < n-k，则我们希望消除掉边

ic_{0}, ic_1, \dots, ic_{p-1}, \quad n-k \le c_i < n.

最直观且自然地，我们会使用团 E = \{i\} \cup \{n-k,n-k+1,\dots,n-1\} \setminus \{c\}，也就是将除了 ic 边以外的状态全都翻转。

若 k 是奇数，根据 H' \in U_k，2 \mid \deg(i)，即 2 \mid p。考虑到可以利用

\begin{aligned} \{i\} \cup \{n-k,n-k+1,\dots,n-1\} \setminus \{c_0\};\\ \{i\} \cup \{n-k,n-k+1,\dots,n-1\} \setminus \{c_1\}. \end{aligned}

两个操作来翻转 ic_0,ic_1 两条边的状态，所以我们一共需要 p 次操作来还原，所以此时的总操作数 \sum p_i \le k(n-k)。

若 k 是偶数，再次分情况讨论：若 p 是偶数，那么根据之前的观察，

\begin{aligned} \{i\} \cup \{n-k,n-k+1,\dots,n-1\} \setminus \{c_0\};\\ \{i\} \cup \{n-k,n-k+1,\dots,n-1\} \setminus \{c_1\}. \end{aligned}

可以翻转 ic_0,ic_1，即得；若 p 是奇数，那么翻转

\{i\} \cup \{n-k,n-k+1,\dots,n-1\} \setminus \{d\}, \text{其中}\ d \notin \{c_0, \dots, c_{p-1}\},

则每一个 c_i 被翻转了 k-p（是奇数）次；每一个 d \notin \{c_0,\dots,c_{p-1}\} 被翻转了 k-p-1（是偶数）次。即得。此时的总操作数 \sum \le \sum \max\{p_i,k-p_i\} \le k(n-k)。

定理 5 的证明. 对于图 H = G + G' 依次使用定理 5 (a) 和定理 5 (b)，就得到一个图 H''，它只在 \{n-k,n-k+1,\dots,n-1\} 之间可能存在边。但是 H'' \in U_k，所以 H'' 只能是 k 阶完全图 K_k 或空图 0。所以最后只需要至多 1 次操作。所以操作数总和为

\binom{n-k}{2} + n(n-k) + 1 \le \binom n2.

精细实现即可做到 \mathrm O(n^3)。