P3812 【模板】线性基

原题链接

• 洛谷 P3812 【模板】线性基

参考资料

• 线性基 - OI Wiki
• Basis (linear algebra) - Wikipedia
• Zassenhaus algorithm - Wikipedia

题意简述

给定 $n$ 个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

解题思路

思想

将每个整数视作 $\mathbb{Z}_2^k$ 中的一个 $k$ 维向量。

在 $\mathbb{Z}_2$ 上，加法 $+$ 等价于按位异或 $\oplus$。

因此，问题可转化为：给定 $n$ 个向量，选择若干个相加，使结果的二进制数值尽可能大。

在线性代数中，这组向量张成一个线性空间。

我们构造它的 线性基（一组两两线性无关且能生成整个空间的最小集合），再利用线性基“高位优先”的结构，贪心求出最大异或值。

构造

维护数列 $p_i$，其中 $p_i$ 表示最高位在第 $i$ 位为 $1$ 的基向量（若不存在则为 $0$）。

插入整数 $x$ 的过程如下：从高位到低位依次检查，如果 $x$ 的第 $i$ 个二进制位为 $1$：

• 若 $p_i=0$，说明这一位还没有基向量，将 $p_i\gets x$，并结束插入；
• 否则，将 $x\gets x\oplus p_i$，把第 $i$ 位消为 $0$，继续向更低位处理。

若最终 $x=0$，说明它可以由已有基向量异或得到（线性相关），无需加入基向量。

查询

令 $s=0$，从高位到低位依次判断，尝试用基向量 增大 答案：

$$s\gets\max(s,s\oplus p_i)$$

证明

数列 $p$ 始终是一组能够张成原集合的基：

• 所有非零 $p_i$ 的主元位互不相同，形成阶梯形结构；
• 任一已处理元素都可以由当前 $p$ 表示（要么成为新的基向量，要么被完全消去）。

从高位到低位的顺序保证：

• 处理到第 $i$ 位时，更高位已确定且最优；
• 若可以通过某个 $p_i$ 使第 $i$ 位从 $0$ 变为 $1$，结果必然更优；
• 这种操作不会影响更高位，低位仍可自由调整。

因此该贪心过程能得到全局最优解。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
const int N=64;
ull p[N];
void insert(ull x)
{
	for(int i=N-1;i>=0;i--)
	{
		if(x>>i&1)
		{
			if(!p[i])
			{
				p[i]=x;
				return;
			}
			x^=p[i];
		}
	}
}
ull query()
{
	ull res=0;
	for(int i=N-1;i>=0;i--)
	{
		res=max(res,res^p[i]);
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		ull t;
		cin>>t;
		insert(t);
	}
	cout<<query()<<'\n';
	return 0;
}