33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:36Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

线性基可以用于处理'''异或'''相关问题，如求最大异或和、第 <math>k</math> 小异或和等。

== 模板 ==

[https://oj.33dai.cn/p/P3812 P3812. 【模板】线性基]

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

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
using namespace std;
const int MAXL = 50;

struct LinearBasis
{
long long a[MAXL + 1];
LinearBasis()
{
std::fill(a, a + MAXL + 1, 0);
}
LinearBasis(long long *x, int n)
{
build(x, n);
}
void insert(long long t)
{
for (int j = MAXL; j >= 0; j--)
{
if (!t)
return;
if (!(t & (1ll << j)))
continue;
if (a[j])
t ^= a[j];
else
{
for (int k = 0; k < j; k++)
if (t & (1ll << k))
t ^= a[k];
for (int k = j + 1; k <= MAXL; k++)
if (a[k] & (1ll << j))
a[k] ^= t;
a[j] = t;
break;
}
}
}
void build(long long *x, int n)
{
std::fill(a, a + MAXL + 1, 0);
for (int i = 1; i <= n; i++)
insert(x[i]);
}
long long queryMax()
{
long long res = 0;
for (int i = 0; i <= MAXL; i++)
res ^= a[i];
return res;
}
void mergeFrom(const LinearBasis &other)
{
for (int i = 0; i <= MAXL; i++)
insert(other.a[i]);
}
};

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
long long n, x;
cin >> n;
LinearBasis lb;
for (int i = 1; i <= n; i++)
{
cin >> x;
lb.insert(x);
}
cout << lb.queryMax() << "\n";
return 0;
}
</syntaxhighlight>

== 使用说明 ==

- <code>insert(x)</code>：向线性基中插入一个数 <math>x</math>
- <code>queryMax()</code>：查询能表示出的最大异或和
- <code>mergeFrom(other)</code>：合并另一个线性基

时间复杂度：插入 <math>O(\log \max)</math>，查询 <math>O(\log \max)</math>。

[[Category:算法模板]]
[[Category:三三文档]]

05-算法模板/07-线性基 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档