我回来填坑啦！
我现在大概理解线性基了。
假设你有一个集合 (S)，那你可以把它压成一个线性基 (P)，然后使得两个集合能异或出来的玩意完全一致。
我们是要按位操作。
假设你 (S = {1,2,3})，那你发现你的 (P = {1,2}) 是可以的。
然后 ({1,3}) 也是可以的。你要明白线性基这玩意不唯一，而且他是不同顺序可能会有多种不同的线性基。
说几个有用的性质先。
- 线性基有 (log) 位，每一位 (p_i) 的最高位是 (2^i) 或者不存在该位
- 因为高位不冲突，所以能构造的数字自然是 (2^{|P|}-1) 个啦！
我们想象一下线性基的过程。线性基一共有 (log) 位对不对。
我们考虑如果 (x) 的最高位为 (2^i) ，如果 (p_i) 是 0，也就是空的基的话。
我们就直接把 (p_i = x)，这样丢进去就好了/cy。
那么如果 (p_i != 0) 怎么办，我们考虑到，如果 (p_i) 是插进去的话，那么他也是原来的元素之一，所以和他异或一下还能是原集合能异或出来的数。
但是如果他是间接插进去的怎么办，它异或过其他数字！不用慌，转化一下，由于那个位置是若干个原集合 (S) 的元素异或得来，当你插入这个元素，和原集合的元素异或的时候，它还是原集合能异或出来的数字对不对。
所以你整个集合都是原集合能异或出来的数字构成的，在特殊情况下，它其实就是原集合的数构成的，当你顺序插入的时候。
所以先异或上，然后你的最高位就没掉了，接着向下循环，直到能插进去位置，如果他插不进去？为什么呢，因为它会变成 (0)。
因为你每一位都是可以控制的，控制的意思大概是指，你的 (i) 位如果有元素，那么你可以选择这一位 (2^i) 是选还是不选，记住，此时你只关心这个最高位。也就是从高位贪心。
如何证明线性基的元素都能异或出来原集合的元素呢？
- 线性基的元素是由原集合构造出来的。
- 原集合有些元素是冲突的，而线性基并没有插入进去线性相关的元素，即能把它扔进去变为0的元素。
我们再考虑，如果你丢进去 ({6,10})，你发现你只能异或出来 ({6,10,12}) 对吧。
你发现如果你丢到线性基里，你的线性基元素也是 ({6,10})，还是只能构造出来这么多。
但是如果你原集合是 ({6,10,12}) 呢？你考虑到，你丢进去6，插入成功了，线性基 ({6})
然后再插入10，显然能丢进去对吧，线性基 ({6,10})，然后我们发现原集合能构造出来是 ({6,10,12})，而你线性基构造出来的还是 ({6,10,12})。
假如，我们要求一个数字，能不能被一个这个集合表示，怎么办，我们就假装插入（雾）
按照插入的姿势，直接丢进去，看有没有一个位置为空，如果有一个位置为空的，直接return 1就好了，否则就return 0
- 如何求最大值
假设原集合能异或出来的数字，线性基也能异或出来，你懂了的话。最大值似乎也不是什么问题。
我们发现 (p_i) 的最高位是 (2^i) 对吧，且其他元素的最高位都不和这个重复。
我们倒着取（这里指倒着循环），如果 (p_i) 这一位存在，我们自然是不取这一个基的，否则就取过来，因为你一个 (2^i geq p_{i-1})，易证，不证明了。
然后你可以有效的控制 (2^i) 这一位到底有没有，因为你 (p_i) 一定存在 (i) 这一位，但是你 (p_j [j geq i]) 也可能存在 (i) 这一位所以不能直接取，要取一个 (max(ans , ans oplus p_i))。
如果我们想求 (k) 大 (k) 小的话，那么我们要去关心 (i) 必须不能被比他大的元素干扰，所以我们要消除这个贡献也就是 (p_i & (2^j) [j < i]) 的时候 (p_i oplus p_j)
LOJ 有个题可以去试试
代码长这个样子
// by Isaunoya
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)
#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)
#define int long long
const int _ = 1 << 21;
struct I {
char fin[_], *p1 = fin, *p2 = fin;
inline char gc() {
return (p1 == p2) && (p2 = (p1 = fin) + fread(fin, 1, _, stdin), p1 == p2) ? EOF : *p1++;
}
inline I& operator>>(int& x) {
bool sign = 1;
char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c & 15);
while ((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15);
x = sign ? x : -x;
return *this;
}
inline I& operator>>(double& x) {
bool sign = 1;
char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c - 48);
while ((c = gc()) > 47) x = x * 10 + (c - 48);
if (c == '.') {
double d = 1.0;
while ((c = gc()) > 47) d = d * 0.1, x = x + (d * (c - 48));
}
x = sign ? x : -x;
return *this;
}
inline I& operator>>(char& x) {
do
x = gc();
while (isspace(x));
return *this;
}
inline I& operator>>(string& s) {
s = "";
char c = gc();
while (isspace(c)) c = gc();
while (!isspace(c) && c != EOF) s += c, c = gc();
return *this;
}
} in;
struct O {
char st[100], fout[_];
signed stk = 0, top = 0;
inline void flush() { fwrite(fout, 1, top, stdout), fflush(stdout), top = 0; }
inline O& operator<<(int x) {
if (top > (1 << 20)) flush();
if (x < 0) fout[top++] = 45, x = -x;
do
st[++stk] = x % 10 ^ 48, x /= 10;
while (x);
while (stk) fout[top++] = st[stk--];
return *this;
}
inline O& operator<<(char x) {
fout[top++] = x;
return *this;
}
inline O& operator<<(string s) {
if (top > (1 << 20)) flush();
for (char x : s) fout[top++] = x;
return *this;
}
} out;
#define pb emplace_back
#define fir first
#define sec second
int n, a[64], p[64];
signed main() {
#ifdef _WIN64
freopen("testdata.in", "r", stdin);
#endif
in >> n;
rep(i, 1, n) in >> a[i];
rep(i, 1, n) {
for (int j = 50; ~j; --j) {
if ((a[i] & (1ll << j))) {
if (!p[j]) p[j] = a[i];
a[i] ^= p[j];
}
}
}
int ans = 0;
for (int i = 50; ~i; --i) ans = max(ans, ans ^ p[i]);
out << ans << '
';
return out.flush(), 0;
}
找个出所有简单环，这样就可以和原有路径抵消掉
最后求异或，没了
// by Isaunoya
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)
#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)
#define int long long
const int _ = 1 << 21;
struct I {
char fin[_], *p1 = fin, *p2 = fin;
inline char gc() {
return (p1 == p2) && (p2 = (p1 = fin) + fread(fin, 1, _, stdin), p1 == p2) ? EOF : *p1++;
}
inline I& operator>>(int& x) {
bool sign = 1;
char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c & 15);
while ((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15);
x = sign ? x : -x;
return *this;
}
inline I& operator>>(double& x) {
bool sign = 1;
char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c - 48);
while ((c = gc()) > 47) x = x * 10 + (c - 48);
if (c == '.') {
double d = 1.0;
while ((c = gc()) > 47) d = d * 0.1, x = x + (d * (c - 48));
}
x = sign ? x : -x;
return *this;
}
inline I& operator>>(char& x) {
do
x = gc();
while (isspace(x));
return *this;
}
inline I& operator>>(string& s) {
s = "";
char c = gc();
while (isspace(c)) c = gc();
while (!isspace(c) && c != EOF) s += c, c = gc();
return *this;
}
} in;
struct O {
char st[100], fout[_];
signed stk = 0, top = 0;
inline void flush() { fwrite(fout, 1, top, stdout), fflush(stdout), top = 0; }
inline O& operator<<(int x) {
if (top > (1 << 20)) flush();
if (x < 0) fout[top++] = 45, x = -x;
do
st[++stk] = x % 10 ^ 48, x /= 10;
while (x);
while (stk) fout[top++] = st[stk--];
return *this;
}
inline O& operator<<(char x) {
fout[top++] = x;
return *this;
}
inline O& operator<<(string s) {
if (top > (1 << 20)) flush();
for (char x : s) fout[top++] = x;
return *this;
}
} out;
#define pb emplace_back
#define fir first
#define sec second
template <class T>
inline void cmax(T& x, const T& y) {
(x < y) && (x = y);
}
template <class T>
inline void cmin(T& x, const T& y) {
(x > y) && (x = y);
}
int n, m;
const int N = 5e4 + 10;
const int M = 1e5 + 10;
int cnt = 0, head[N];
struct Edge {
int v, nxt, w;
} e[M << 1];
int d[N], p[65];
bool vis[N];
void add(int u, int v, int w) {
e[++cnt] = { v, head[u], w }, head[u] = cnt;
e[++cnt] = { u, head[v], w }, head[v] = cnt;
}
void insert(int val) {
for (int i = 63; ~i; --i)
if (val & (1ll << i)) {
if (!p[i]) p[i] = val;
val ^= p[i];
}
}
void dfs(int u, int cur) {
d[u] = cur, vis[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (vis[v])
insert(cur ^ e[i].w ^ d[v]);
else
dfs(v, cur ^ e[i].w);
}
}
int query(int val) {
int res = val;
for (int i = 63; ~i; --i) cmax(res, res ^ p[i]);
return res;
}
signed main() {
#ifdef _WIN64
freopen("testdata.in", "r", stdin);
#endif
in >> n >> m;
int u, v, w;
while (m--) {
in >> u >> v >> w, add(u, v, w);
}
dfs(1, 0);
out << query(d[n]) << '
';
return out.flush(), 0;
}
留一些坑。
洛谷P3857 [TJOI2008]彩灯
洛谷P4301 [CQOI2013]新Nim游戏
CF895C Square Subsets
洛谷P4570 [BJWC2011]元素
洛谷P3265 [JLOI2015]装备购买
洛谷P3292 [SCOI2016]幸运数字
洛谷P4151 [WC2011]最大XOR和路径
CF724G Xor-matic Number of the Graph
CF938G Shortest Path Queries