线性基学习 洛谷:P3812 模板(线性基)
程序员文章站
2022-04-15 19:18:39
线性基:#include #include #include #include #include
线性基:
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int maxn = 1e6 + 5;
pair<int, int> p;
ll a[65], d[65];
void Insert(ll x) //构造线性基
{
for (ll i = 60; i >= 0; i--)
{
if ((x >> i) & 1ll)
{
if (!d[i])
{
d[i] = x;
break;
}
else
{
x ^= d[i];
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n, x;
cin >> n;
for (ll i = 0; i < n; i++)
{
cin >> x;
Insert(x);
}
ll ans = 0;
for (ll i = 60; i >= 0; i--)
{
if ((ans ^ d[i]) > ans)
{
ans ^= d[i];
}
}
cout << ans << endl;
}
本文地址:https://blog.csdn.net/yangzijiangac/article/details/107376508