[洛谷P3812] 【模板】线性基

P3812 【模板】线性基

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

(1leq nleq50, 0leq a_ileq 2^{50})

做法

显然重复不重复没有什么区别。

直接套线性基板子。

#include <iostream>
using namespace std;
typedef long long type;
const int W = 51;
type basis[W + 1];
void ins(type x)
{
    for (int i = W; i >= 1; i--)
    {
        if (x >> (i - 1))
        {
            cerr << i << endl;
            if (basis[i] == 0)
            {
                basis[i] = x;
                return;
            }
            x ^= basis[i];
        }
    }
}
type maxxor()
{
    type ans = 0;
    for (int i = W; i >= 1; i--)
    {
        ans = max(ans, ans ^ basis[i]);
    }
    return ans;
}
int n;
type x;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        ins(x);
        cerr << i << endl;
    }
    cout << maxxor() << endl;
}