标签:# 线性基

「AtCoder 141F」Xor Sum 3

We have N non-negative integers: A1,A2,…,AN.

Consider painting at least one and at most N−1 integers among them in red, and painting the rest in blue.

Let the beauty of the painting be the [mbox][mbox]XOR of the integers painted in red, plus the [mbox][mbox]XOR of the integers painted in blue.

Find the maximum possible beauty of the painting.

Read More ~

「Template」线性基

#include <cstdio> using namespace std; typedef long long ll; struct Line_base { ll b[64],cnt; Line_base() { memset(b, 0, sizeof(b)); cnt = 0; } void Insert(ll x) { for (int i = 62; i >= 0; i--) { if (x&(1LL << i)) { if (b[i])x ^= b[i]; else { b[i] = x; cnt++; break; } } } } bool check(ll x) { for (int i = 62; i >= 0; i--) { if (x&(1LL << i)) { if (!b[i])return false; else x ^= b[i]; } } return true; } //交集 friend Line_base operator & (const Line_base &a, const Line_base &b) { Line_base ans, c = b, d = b; for (int i = 0; i < 62; i++) { ll x = a.b[i]; if (!x)continue; int j = i; ll T = 0; for (; j >= 0; --j) if ((x >> j) & 1) if (c.b[j]) { x ^= c.b[j]; T ^= d.b[j]; } else break; if (!x)ans.b[i] = T,ans.cnt++; else c.b[j] = x,d.b[j] = T; } return ans; } }; int main() { return 0; }
Read More ~