题解：P12044 [USTCPC 2025] Algorithm Duel

宣传博客：USTCPC25 F&K 题解

这题是寒假想到的，USTCPC 赛前听说缺题，突然感觉可以出成妙妙构造题。但是当时事情有点多，因此题面和数据都是 @Grand_Dawn 写的，感谢（

如下是该题的一个等价转换：

设 $n \ge 3(d - 1)$，且 $V \subset \mathbf{F}_2^n$ 是一个维度为 $d$ 的线性子空间。那么，存在一个向量 $\mathbf{x} \in V$，使得其 Hamming weight 满足：

取 $V$ 的一组行最简形式（保证主元对应的列消的只剩下一个 1，可以参考 Menci 的写法）下的线性基 $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d$。因为每个基向量中至少有 $d-1$ 个 0，所以可以保证每个基向量的 Hamming weight 满足：

接下来讨论两种情况：

存在某个 $i$，使得 $|\mathbf{b}_i| \in [d, n - d + 1]$。此时，$\mathbf{b}_i$ 本身即满足结论。

对于所有 $i$，都有 $|\mathbf{b}_i| \in [1, d - 1]$，即每个基向量的 Hamming weight 都小于 $d$。定义如下的前缀和向量：

由于每个 $\mathbf{b}_i$ 的 Hamming weight 小于 $d$，所以相邻两个前缀和向量之间的 Hamming weight 差满足：

又因为基底是行最简的形式，可以保证 $\mathbf{x}_d$ 至少有 $d$ 个非零位，即：

因此，由于 Hamming weight 从 $0$ 增加到至少 $d$，且每一步变化最多为 $d - 1$，根据离散中值定理，存在某个 $k \in [d]$，使得：

所以存在一个满足条件的向量 $\mathbf{x} = \mathbf{x}_k \in V$，证毕。

最终算法就呼之欲出了，先进行高斯消元，随后检查每个向量以及前缀异或和是否满足条件即可，复杂度 $O(\frac{n^3}{w})$。