前
线性基就相当于向量的基底，且表示的范围与原来表示的范围相同。
插入线性基的过程本质上还是高斯消元，如果被消成全是 \(0\) 就说明这个向量能被其他向量线性表示。
模板
这里 \(a_i\) 表示第 \(i\) 位为 \(1\) ,前面的全是 \(0\) 。
void in(ll x){
for(int i=63;i>=0;i--)
if(x>>i&1){
if(a[i]) x^=a[i];
else{
for(int j=0;j<i;j++) if(x>>j&1) x^=a[j];
for(int j=i+1;j<=63;j++) if(a[j]) a[j]^=x;
a[i]=x;
return;
}
}
}
[WC2011] 最大XOR和路径
题目描述
XOR（异或）是一种二元逻辑运算，其运算结果当且仅当两个输入的布尔值不相等时才为真，否则为假。 XOR 运算的真值表如下（\(1\) 表示真， \(0\) 表示假）：
| 输入 | 输入 | 输出 |
|---|---|---|
| A | B | A XOR B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
而两个非负整数的 XOR 是指将它们表示成二进制数，再在对应的二进制位进行 XOR 运算。
譬如 \(12\) XOR \(9\) 的计算过程如下：
\[12=(1100)_2\ \ \ 9=(1001)_2\\ \begin{matrix} &1\ 1\ 0\ 0\\ \text{XOR}&1\ 0\ 0\ 1\\ \hline &0\ 1\ 0\ 1\\ \end{matrix}\\ (0101)_2=5 \]故 \(12\) XOR \(9 = 5\)。
容易验证， XOR 运算满足交换律与结合律，故计算若干个数的 XOR 时，不同的计算顺序不会对运算结果造成影响。从而，可以定义 \(K\) 个非负整数 \(A_1\)，\(A_2\)，……，\(A_{K-1}\)，\(A_K\)的 XOR 和为
\(A_1\) XOR \(A_2\) XOR …… XOR \(A_{K-1}\) XOR \(A_K\)
考虑一个边权为非负整数的无向连通图，节点编号为 \(1\) 到 \(N\)，试求出一条从 \(1\) 号节点到 \(N\) 号节点的路径，使得路径上经过的边的权值的 XOR 和最大。
路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数，具体见样例。
输入格式
输入文件 xor.in 的第一行包含两个整数 \(N\) 和 \(M\)， 表示该无向图中点的数目与边的数目。
接下来 \(M\) 行描述 \(M\) 条边，每行三个整数 \(S_i\)， \(T_i\) ， \(D_i\)， 表示 \(S_i\) 与 \(T_i\) 之间存在一条权值为 \(D_i\) 的无向边。
图中可能有重边或自环。
输出格式
输出文件 xor.out 仅包含一个整数，表示最大的 XOR 和（十进制结果）。
样例 #1
样例输入 #1
5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2
样例输出 #1
6
提示
【样例说明】
如图，路径\(1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 5\)对应的XOR和为
\(2\) XOR \(1\) XOR \(2\) XOR \(4\) XOR \(1\) XOR \(1\) XOR \(3 = 6\)
当然，一条边数更少的路径\(1 \rightarrow 3 \rightarrow 5\)对应的XOR和也是\(2\) XOR \(4 = 6\)。
【数据规模】
对于 \(20 \%\) 的数据，\(N \leq 100\)， \(M \leq 1000\)，\(D_i \leq 10^{4}\)；
对于 \(50 \%\) 的数据，\(N \leq 1000\)， \(M \leq 10000\)，\(D_i \leq 10^{18}\)；
对于 \(70 \%\) 的数据，\(N \leq 5000\)， \(M \leq 50000\)，\(D_i \leq 10^{18}\)；
对于 \(100 \%\) 的数据，\(N \leq 50000\)， \(M \leq 100000\)，\(D_i \leq 10^{18}\)。
题解
因为环是可选可不选的，所以把环存进线性基，在任意一条从 \(1-n\) 的路径中，用这条路径 \(XOR\) 环，如果值能变大就加上去。如果还有一条路径，那么可以通过 \(XOR\) 这两条路径构成的环转换。
code
#include<iostream>
using namespace std;
typedef long long ll;
const int N=50005;
const int M=200005;
int n,m,head[N],cnt;
bool vis[N];
ll d[N],ans,a[65];
struct edge{
int next,v;
ll w;
}e[M];
void add(int u,int v,ll w){
cnt++;
e[cnt].next=head[u];
e[cnt].v=v;
e[cnt].w=w;
head[u]=cnt;
}
void in(ll x){
for(int i=63;i>=0;i--)
if(x>>i&1){
if(a[i]) x^=a[i];
else{
for(int j=0;j<i;j++) if(x>>j&1) x^=a[j];
for(int j=i+1;j<=63;j++) if(a[j]) a[j]^=x;
a[i]=x;
return;
}
}
}
void dfs(int x,ll sum){
vis[x]=1;d[x]=sum;
for(int i=head[x];i;i=e[i].next){
int to=e[i].v;
if(vis[to])
in(sum^e[i].w^d[to]);
else
dfs(to,sum^e[i].w);
}
}
int main(){
int u,v;ll w;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs(1,0);
ans=d[n];
for(int i=63;i>=0;i--)
if(!(ans>>i&1))
ans^=a[i];
printf("%lld",ans);
}