解题思路

指纹值小于 $2^{12}$ ，所有可能的异或结果只有 $V=4096$ 种。对每个异或值 $x$ ，维护达到它的最少选取件数 $\mathrm{min\_t}[x]$ 与最多选取件数 $\mathrm{max\_t}[x]$ 。

用 $0/1$ 背包在异或维上转移：对当前指纹 $v$ ，

$\mathrm{new\_min}[x]=\min(\mathrm{old\_min}[x],\mathrm{old\_min}[x \oplus v]+1)$
$\mathrm{new\_max}[x]=\max(\mathrm{old\_max}[x],\mathrm{old\_max}[x \oplus v]+1)$

题目内容

有 $n$ 块信号模块，每块都带有相同的基础增益 $b$ ，第 $i$ 块的指纹值为 $a_i$ 。选择其中 $t$ 块（不可重复），记所选指纹为 $a_{i_1}, \ldots, a_{i_t}$ ，则总增益为

(a_{i_1} \oplus a_{i_2} \oplus \cdots \oplus a_{i_t}) + b \times t

其中 $\oplus$ 表示按位异或。也可以一块都不选，此时总增益为 0。

请在总增益最大的前提下，使所选模块数 $t$ 尽可能少，并同时输出这个最少模块数与最大总增益。

约束：测试组数不超过 20，单组模块数不超过 10^3，基础增益 $b$ 满足 $-25 \le b \le 25$ ，指纹值满足 $0 \le a_i < 2^{12}$ ，且单个测试文件中模块数之和不超过 10^3。