省选联考 2026《星图》：GF(2) 可达空间与构造消元

本节目标

学会把“反转一个 $k$ 点完全图”视为 GF(2) 向量加法，找出与 $k\bmod4$ 有关的全部不变量；在可达等价类中构造边数最大的图，再用“逐点消元+最后 $k+2$ 点闭式求解”产生不超过 $\binom n2$ 次操作。

前置知识与课前自测

前置：位向量、GF(2) 线性空间、图的度数奇偶性、简单构造。

反转 $k$ 个点之间的全部边，总边数的奇偶性改变当且仅当哪个量为奇数？
一次操作使每个被选顶点的度数改变 $k-1$ 的奇偶性；因此什么时候每个顶点的度奇偶都不变？
给定一个图中奇度顶点的集合，最少需多少条边实现它？

答案

1. $\binom k2$；它在 $k\equiv2,3\pmod4$ 时为奇数。 2. $k$ 为奇数时，$k-1$ 为偶数。 3. 若奇度点数为 $2r$，至少 $r$ 条，用一个匹配可达到。

问题动机

边数至多只有 $\binom{500}{2}$，但不能对这么多变量直接做稠密高斯消元，更不能在一个余集中做最大 Hamming 重量搜索。题目操作具有强对称性：所有 $k$ 元点集都可选。这提示我们不应求一个任意矩阵的基，而应先找置换对称下可能存在的少数奇偶不变量。

步步式引导

1. 把图写成位向量

给定所有无序点对一个固定顺序，图 $G$ 是长 $M=\binom n2$ 的 0/1 向量。对 $k$ 元集 $S$，操作向量 $C_S$ 在 $S$ 内部边上为 1。多次操作的顺序不重要，两次相同操作抵消，最终变化为

$$ D=\bigoplus_{S\in\mathcal A}C_S. $$

因此问题分成两步：先在余集 $G+span{C_S}$ 中找最多边的目标图，再把差分 $D$ 表示成操作向量之和。

2. 两类直接不变量

一次操作反转 $\binom k2$ 条边，所以当 $k\equiv0,1\pmod4$ 时，总边数奇偶不变。

每个被选顶点的度改变 $k-1$ 条，所以当 $k$ 为奇数时，每个顶点的度奇偶不变。四种余数类得到：

$k\bmod4$	总边数奇偶	各点度奇偶
0	不变	可改变
1	不变	不变
2	可改变	可改变
3	可改变	不变

此时还不能直接宣布“没有其他不变量”。这个充分性将由后面的显式消元构造证明：只要差分满足表中必要条件，构造一定能把它消为空。

3. 反过来研究“缺哪些边”

最大化目标图 $T$ 的边数，等价于最小化完全图相对于 $T$ 的缺边图 $H=K_n-T$。这一反向建模把“尽量多”改成了小图构造。

若度奇偶需保持，则 $H$ 中顶点 $v$ 必须具有的度奇偶为

$$ q_v=(n-1\bmod2)\oplus deg_G(v)\bmod2. $$

设 $q_v=1$ 的顶点有 $2r$ 个。用 $r$ 条不相交边两两配对，就是实现这组度奇偶的最少缺边。

若还要求 $|H|$ 的奇偶，但 $r$ 的奇偶不对：

$r>0$ 时，把匹配边 $(a,b)$ 替换为长为 2 的路径 $(a,x),(x,b)$，边数加 1，所有度奇偶不变。
$r=0$ 且需奇数条缺边时，最小非空奇边数偶度图是三角形，需 3 条边。

核心知识

逐点消元：为什么每次能清空一个顶点

当尚有 $h>k+2$ 个顶点时，选一个顶点 $v$。只使用包含 $v$ 的操作；每个操作在其余 $h-1$ 点中选 $r=k-1$ 个。我们先只看它对 $v$ 的关联边的影响，这就是一个 $r$ 元集的指示向量。

取基集 $B$，$|B|=r$，固定 $b_0\in B$ 和 $x_0\notin B$。只需考虑以下 $h-1$ 个候选：

$$ B, $$

$$ B-{b_0}+{x}\quad(x\notin B), $$

$$ B-{b_i}+{x_0}\quad(b_i\in B-{b_0}). $$

任意候选向量与 $B$ 异或，会得到一对顶点。这些对生成所有偶重向量；若 $r$ 为奇数，再加上奇重的 $B$，便生成所有向量。这与必要不变量完全对齐：

$k$ 偶，$r$ 奇：可任意修改 $v$ 的关联边。
$k$ 奇，$r$ 偶：只能修改偶数条关联边；而度奇偶不变正好保证待消向量为偶重。

选出系数后，把 $v$ 的所有差分边消成 0，不再使用 $v$。操作会改变剩余顶点之间的差分，但这只是把未解部分换成同一余集中的另一个实例，不破坏不变量。

最后 $k+2$ 点：补集点对化

当剩 $h=k+2$ 点时，一个 $k$ 元操作恰好等于“排除两个顶点 $a,b$”。令 $x_{ab}$ 表示是否使用该操作，定义

$$ X=\bigoplus{a<b}x{ab}, $$

$$ Ru=\bigoplus{v\ne u}x_{uv}. $$

边 $(u,v)$ 只被“排除点对与 $u,v$ 不相交”的操作反转，因此待消差分 $D_{uv}$ 满足

$$ D_{uv}=X\oplus R_u\oplus Rv\oplus x{uv}. $$

只需枚举 $X\in{0,1}$。若 $h$ 为偶数，对每个 $u$ 有 $R_u=deg_D(u)\oplus X$；若 $h$ 为奇数，可取全部 $Ru=0$，而可行性由度不变量保证。代回上式即得全部 $x{uv}$，再检查异或和是否确为 $X$。

操作数上界

当前有 $h$ 个顶点时，消掉一点最多用 $h-1$ 个候选操作。最后 $k+2$ 点最多使用每个排除点对一次，所以

$$ \sum_{h=k+3}^{n}(h-1)+\binom{k+2}{2}=\binom n2. $$

题面保证 $p\ge\binom n2$，因此构造严格满足次数限制，不需随机化或希望步数分析。

精选例题：星图 / starmap

来源信息、题意与范围

洛谷-P15653 星图 / starmap，省选联考 2026，交互库题。
$4\le n\le500$，单点内 $\sum n\le3000$；$2\le k\le n-2$，$\binom n2\le p\le2\times10^5$。
每次恰选 $k$ 个不同顶点，反转它们之间所有边。先报告可达图的最大边数，再在 $p$ 次内把图变到该边数。

Hint 1：操作顺序不重要

边状态是 GF(2)，一个 $k$ 元集至多使用一次。

Hint 2：先列不变量

分别计算操作对总边数奇偶和每点度奇偶的影响，按 $k\bmod4$ 分类。

Hint 3：构造目标图

从完全图减去一个最小的缺边图；缺边图只需实现指定的度奇偶与边数奇偶。

Hint 4：构造操作

在多于 $k+2$ 点时消掉一个顶点的全部差分边；剩 $k+2$ 点时，用“每个操作排除两点”建方程。

Observations

若只找到不变量，得到的只是上界；逐点消元是兼具“无其他不变量”证明和实际操作序列的充分性证明。
最大边图本身可能很大，但它的缺边图只是空图、一条边、一个匹配、一条长 2 路径替换或三角形。反向研究把优化变成了局部构造。
消元不是使用 $M\times\binom nk$ 矩阵；它为每个顶点现场构造一个至多 $h-1$ 个向量的显式基，删掉了高斯消元的立方维度。
最后 $k+2$ 点之所以特别，不是数据范围的偶然，而是 $k$ 元集的补集恰好是一条边；变量因而与待消边一一对应。

Editorial 与正确性证明

按 $k\bmod4$ 构造最小缺边图 $H$，得到目标 $T=K_n-H$。前述下界证明 $H$ 的边数不可更少：每条缺边最多配对两个奇度要求，而边数奇偶不匹配时下一个可能边数至少多 1；无奇度点时，非空偶度简单图至少含一个环，奇边数最小环是三角形。所给匹配/路径/三角形均达到下界，故 $T$ 边数最大。

令 $D=G\oplus T$。目标构造保证 $D$ 的必要奇偶量全为 0。逐点消元时，显式基能生成当前顶点所有允许的关联向量，故一定能清空该顶点。归纳后只剩 $k+2$ 点；补集点对方程枚举两个 $X$ 值，而不变量保证其中至少一个自洽。因此全部 $D$ 被消掉，最终图恰为 $T$。操作数恒不超过 $\binom n2\le p$。

实现指南

target = complete_graph minus minimum missing graph required by invariants
D = initial XOR target
remaining = all vertices
while len(remaining) > k+2:
    v = remove one vertex
    B = any (k-1)-subset of remaining
    build the h-1 candidate subsets from B by one-element replacements
    solve their coefficients by XOR formulas
    apply selected k-cliques containing v; now every D[v,*] is zero
for X in {0,1}:
    derive R and x[excluded_pair] from D[u,v] = X XOR R[u] XOR R[v] XOR x[u,v]
    if self-consistent:
        apply every operation whose excluded-pair variable is 1
        break
report number of edges in target

完整 C++17 本地协议附件

附件是可独立编译的本地 grader 版：读取下发文件的 c,t 协议，在内存中执行所有操作，输出 报告边数是否校验成功。在原评测中应保留核心求解函数，把本地执行器替换为题面的 report/invert 调用。

实现时还要注意：

顶点集必须恰有 $k$ 个互不相同的编号。
官方 grader 中顶点从 1 开始，线性代数实现用 0 下标时要在接口处统一转换。
操作序列可达 $O(n^2)$ 条，官方 grader 用位集合反转；本地矩阵版重在可读性，大压测应同样换成位集合行。
已运行 starmap.zip 中全部 8 个下发输入，每组报告边数与 .ans 一致，本地最终图检查均为 1。这只是本地协议验证，不声称已通过原交互评测。

扩展与联系

本题的不变量是操作空间的正交补观点；构造消元给出了该正交补确实只由边奇偶和度奇偶生成的构造性证明。
“尽量接近完全图”改为“构造最小缺边图”，是补图/对偶建模的典型。
若每次可以选“至多 $k$ 个点”而非恰好 $k$ 个，操作空间会显著增大，这些模 4 分类将不再直接适用。

总结与自检

为什么 $k\equiv1\pmod4$ 时“度奇偶+边数奇偶”是两组独立信息？
奇度要求为空且缺边数必须为奇数时，为什么 1 或 2 条缺边都不行？
逐点消元中，$k$ 奇时为什么待消的关联向量一定为偶重？
最后 $k+2$ 点公式中，为什么 $R_u\oplus Rv$ 没有正确计入 $x{uv}$，需再额外异或一次 $x_{uv}$？
请不看公式，重新推出操作数上界为什么恰是 $\binom n2$。

课后训练建议

先对 $n\le8$ 建出所有 $k$ 元操作向量，用 GF(2) 高斯消元求秩，检查四种 $k\bmod4$ 的余维数。
40 分钟内只做“最优目标图”：为每种余数类写出缺边图，并用下界证明最优。
构造部分卡住 25 分钟后看 Hint 4；再卡住时先推最后 $k+2$ 点的补集点对方程，不要直接阅读附件系数公式。

10-省选2026星图与GF2可达空间.md 10 KB Historie Surový