题解：P12044 [USTCPC 2025] Algorithm Duel
ethan_zhou
·
·
题解
宣传博客：USTCPC25 F&K 题解
这题是寒假想到的，USTCPC 赛前听说缺题，突然感觉可以出成妙妙构造题。但是当时事情有点多，因此题面和数据都是 @Grand_Dawn 写的，感谢（
如下是该题的一个等价转换：
命题
设 n \ge 3(d - 1)，且 V \subset \mathbf{F}_2^n 是一个维度为 d 的线性子空间。那么，存在一个向量 \mathbf{x} \in V，使得其 Hamming weight 满足：
d \le |\mathbf{x}| \le n - d + 1.
证明
取 V 的一组行最简形式（保证主元对应的列消的只剩下一个 1，可以参考 Menci 的写法）下的线性基 \mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d。因为每个基向量中至少有 d-1 个 0，所以可以保证每个基向量的 Hamming weight 满足：
|\mathbf{b}_i| \le n - (d - 1) = n - d + 1.
接下来讨论两种情况：
情况 1：
存在某个 i，使得 |\mathbf{b}_i| \in [d, n - d + 1]。此时，\mathbf{b}_i 本身即满足结论。
情况 2：
对于所有 i，都有 |\mathbf{b}_i| \in [1, d - 1]，即每个基向量的 Hamming weight 都小于 d。定义如下的前缀和向量：
\mathbf{x}_k = \sum_{j = 1}^{k} \mathbf{b}_j, \quad 1 \le k \le d.
由于每个 \mathbf{b}_i 的 Hamming weight 小于 d，所以相邻两个前缀和向量之间的 Hamming weight 差满足：
\left|\, |\mathbf{x}_k| - |\mathbf{x}_{k-1}| \,\right| \le |\mathbf{b}_k| < d.
又因为基底是行最简的形式，可以保证 \mathbf{x}_d 至少有 d 个非零位，即：
|\mathbf{x}_d| \ge d, \quad |\mathbf{x}_0| = 0.
因此，由于 Hamming weight 从 0 增加到至少 d，且每一步变化最多为 d - 1，根据离散中值定理，存在某个 k \in [d]，使得：
|\mathbf{x}_k| \in [d, n - d + 1].
所以存在一个满足条件的向量 \mathbf{x} = \mathbf{x}_k \in V，证毕。
算法
最终算法就呼之欲出了，先进行高斯消元，随后检查每个向量以及前缀异或和是否满足条件即可，复杂度 O(\frac{n^3}{w})。