launched on 2023.8.30 11:20
参考资料：
什么是线性基
这里的线性基指的是 OI 中常用的异或线性基。
个人认为有点类似于向量中的基底，异或线性基就是一组数的集合，每个序列至少有一个线性基，取线性基中的一些数异或起来可以得到原序列中的任意一个数。
线性基的三大性质
异或线性基有一些性质：
- 原序列里的任意一个数都可以由线性基里的一些数异或得到。
- 线性基里面的任意一些数异或起来都不能得到 \(0\)。
- 线性基里面的数个数唯一，且保证性质一的前提下，数的个数最少。
那么想必你已经会了线性基，我们直接开始看例题并讲解吧！
例题
P3812:线性基模板
我们先找到这个序列的线性基，然后从高到位找大的位，找大的位的时候可能会改变小的位，不过问题不大，因为 \((10000)_2>(01111)_2\)，所以我们可以保证这样构造的线性基是最优的。
具体的：
建线性基
用 \(a_i\) 表示二进制下最高位为第 \(i\) 位的线性基元素，我们因为这里求的是最大值，所以不难想到从高位到低位建线性基。
结合代码理解：
void add(ll x){
for(int i=50;~i;--i)//从高位到低位枚举
if((x>>i)&1)//如果这一位是 1 才可能会产生变化或者贡献
if(!a[i])return a[i]=x,void();//如果这一位没有，刚好加入
//然后直接退出，线性基内的元素不能互相更新
else x^=a[i];//否则用 a[i] 更新 x,保证其最高位小于等于 i
}
查询最大值
也是从高位到低位找，如果这一位没有就用线性基更新答案，之后的更新不会影响前面的位，非常巧妙，因为我们在建立的时候保证了 \(a_i\) 的最高位为 \(i\) 自然不会对大于 \(i\) 的部分造成影响。
ll query(){
ll res=0;//一开始的数
for(int i=50;~i;--i)
if(!((res>>i)&1))res^=a[i];//如果这一位为0就用a[i]更新答案，a[i]为0反正不会对答案造成影响，也不需要特判
return res;
}
这样做，我们尽可能保证最高位都是 1 了，所以可以保证最大。
P3857 彩灯
题意即给你一些二进制数，问通过彼此异或最多能表示成多少种数。
因为这并没有让你求最值之类的，所以随便从大，从小建线性基都是可以的，因为我们线性基内存的是 \(a_i\) 表示最高位（或者最低位）为 \(i\) 的数，我们可以控制这些位选或者不选，所以最终答案其实就是 \(2^\text{建出来线性基内元素个数}\)。
int cnt;
void add(ll x){
for(int i=50;~i;--i)
if((x>>i)&1)
if(!a[i])return a[i]=x,cnt++,void();
else x^=a[i];
return;
}
P4301：新 \(Nim\) 游戏
注意到不管怎样先手是一定输不了的，所以不可能输出 -1（我不管你几堆都变成一堆就不可能输）。
那么我们考虑 \(Nim\) 游戏的必败态：异或和为 0。也就是我们拿了之后，不能让对手有可以拿走一些堆使得剩下的部分异或和为 0 的情况。
也就是先手剩下的堆彼此之间无论怎么异或都不能为 0？
在床上辗转反侧，突然恍然大悟：
线性基第二条性质：
- 线性基里面的任意一些数异或起来都不能得到 $0$。
那就建一个线性基，然后我们留下线性基里面的元素即可。因为对于任意一个非空序列一定有线性基，所以不用担心有必须全部取完的情况。
但是怎样最大呢？很容易想到一个想法就是从大到小加入线性基，看看能不能。这样为什么最优？我们不难发现，对于一个序列，线性基的元素个数是唯一的，但是内容不唯一，那假设我们不往里面放最大的，那就空出来了一个位给小的，此时小的放进去了肯定不是最优的，所以我们从大到小看能不能放即可。判能不能放很简单，就看能不能插进线性基里面即可。
int n,a[101],w[33];
ll ans;
bool add(int x){
for(int i=30;~i;--i)
if((x>>i)&1)
if(!w[i])return (w[i]=x)||1;//如果放的进去就可以不要
else x^=w[i];
return 0;//如果最后可以被表示，说明假设放进去一定可能异或为 0，必须拿走
}
int main(){
n=read();
for(int i=1;i<=n;i++)
ans+=(a[i]=read());//先全部拿走
sort(a+1,a+1+n);
for(int i=n;i;--i)//从大到小一个一个加入线性基
if(add(a[i]))ans-=a[i];
cout<<ans;
}
P4570:元素
这题和上一题思路基本一致，不过这次是在线性基内的我们才能加入答案。
typedef long long ll;
typedef pair<ll,ll> PII;
int n;
ll w[65],ans;
PII a[1002];
bool add(ll x){
for(int i=62;~i;--i)
if(x>>i&1)
if(!w[i])return (w[i]=x)||1;
else x^=w[i];
return 0;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i].second=read(),a[i].first=read();
sort(a+1,a+1+n);
for(int i=n;i;--i)
if(add(a[i].second))
ans+=a[i].first;
printf("%d",ans);
}
进阶：P4151 最大XOR和路径
无向联通图的 dfs 树
取任意点为起点，跑一遍 dfs（不能重复经过同一点），走出来的就是一棵 dfs 树。
此时树边已经被分成了两种边：树边和非树边。
有向图的 dfs 树的非树边有三种：横叉边，返祖边，前向边（指向后代）。
因为 dfs 的性质，所以无向图的 dfs 树没有横叉边（假如有，那么先遍历到的会通过这条边把它变成自己的子树，此时又变成了返祖边）。
还有一个性质，每条返祖边都对应了一个环，这个图的所有环都可以通过这些环异或出来。
解法
我们发现，我们先随便找到一条从 \(1-N\) 的路径。因为是联通的，所以我们可以随便从一个分支走到一个环，再从那个环走回来，这样路径上的值不会对我们造成贡献，因为走了两遍，而所有的环都能对我们造成贡献，所以我们把所有环都加入线性基中即可。
不需要找全部的环，因为用返祖边对应的环可以将所有的环都异或出来，符合线性基性质，所以我们只需要把所有这样的环都加入线性基即可。
typedef long long ll;
typedef pair<int,ll> PII;
int n,m;
ll w[65],a[50004];
vector<PII>F[50004];
bool vis[50004];
void add(ll x){//线性基模板
for(int i=62;~i;--i)
if(x>>i&1)
if(!w[i])return w[i]=x,void();
else x^=w[i];
return;
}
ll query(ll x){//尽可能扩大
for(int i=62;~i;--i)
if(!(x>>i&1))x=x^w[i];
return x;
}
void dfs(int x,int fa,ll res){
vis[x]=1;a[x]=res;
for(PII PI:F[x]){
int y=PI.first;ll w=PI.second;
if(y==fa)continue;
if(!vis[y])dfs(y,x,res^w);//没有访问就去访问
else add(res^w^a[y]);//否则就是返祖边，把环加入线性基
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
ll w=read();
F[u].push_back({v,w});
F[v].push_back({u,w});
}
dfs(1,0,0);
cout<<query(a[n]);
return 0;
}
后记
基础部分就这么多了，难的我也不会。
finished on 2023.8.30 15:05