【题解】【模板】线性基 LUOGU – 3812

题目链接

复习线性基突然发现博客居然没有线性基模板代码

于是就水了一发博客

#include <bits/stdc++.h>

#define NS (55)
#define BS (50)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n;

LL basis[BS + 1], ans;

void insert(LL x)
{
    for (int i = BS; i >= 0; i -= 1)
        if (x >> i & 1)
        {
            if (basis[i]) x ^= basis[i];
            else {basis[i] = x; break;}
        }
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1) {LL x; IN(x), insert(x);}
    for (int i = BS; i >= 0; i -= 1)
        if ((ans ^ basis[i]) > ans) ans ^= basis[i];
    printf("%lld\n", ans);
    return 0;
}

溜了溜了