线性基
GavinZheng敲懒的。。。
模板代码引自menci:
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;
}
}
}
// 数组 x 表示集合 S,下标范围 [1...n]
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]);
}
static LinearBasis merge(const LinearBasis &a, const LinearBasis &b)
{
LinearBasis res = a;
for (int i = 0; i <= MAXL; i++) res.insert(b.a[i]);
return res;
}
};