(仅以此篇表愚见)
(笔者希望你在看这个之前学过了高斯消元)
我们先把线性基放到一边，如何用高斯消元解决呢?
（下面的陈述可能有些问题，某些细节和实现希望读者自己想一下）
---->从高到低确定每一位是否能选，即设这一位方程的右边为1，解当前的方程组判断是否有解，一共是解60次方程组\(O(n \cdot 60^3)\)
---->优化：保证消元时不将之前能异或得到的数重新列方程，这样最多只有60个数，即\(O(60^4)\)
---->线性基基本上就是实现了这种优化，并将其广泛应用了
\[ \ \]
\[ \ \]
线性基就是用很少的数做基底 ,通过异或后能够与原数组的数一一对应
通过它们之间的互相异或也就能够得到原数组的异或情况
这种基底的本质就是实现了：若之前出现的数的组合能够得到自己，就把自己扔掉(就是引子讲的优化)
所以其实线性基是最大"独立数"集，用它也可以求出序列不同异或和的个数
\[ \ \]
\[ \ \]
设线性基中的数为\(d[i]\)
这里为了方便联系代码实现,我们设二进制位从第0位开始
1.\(d[i]\)数组不一定是满的
2.线性基中 , 如果第\(i\)个数\(d[i]\)存在,那么\(d[i]\)的第\(i\)位一定是其最高位(不为0)
3.线性基中的元素之间异或不会得到0
4.线性基的元素是在保证能够满足对应关系情况个数最少的
\[ \ \]
\[ \ \]
插入的两种决策
当\(x\)的第\(i\)位大于\(0\)
---->如果第\(i\)还没有存下的\(1\),就把当前数存下来
---->否则这一位的\(1\)要用原来的\(d[i]\)异或掉
\[ \ \]
\[ \ \]
又回到了引子
首先当然是预处理了线性基，但是我们这里不用真的把高斯消元搬出来了
由于通过d[i]数组的异或我们可以得到原数组的所有可能异或答案,所以直接在d[i]数组上贪心就好了
贪心策略还是比较明显的,如果这一位有\(d[i]\)，那么一定要拿
你会发现\(d[i]\)会与之后的\(d[j]\)冲突（因为d[i]后面的1会与d[j]异或抵消）
这时我们有两种解决方法
->
ll ans=0; drep(i,60,0) if((ans^d[i])>ans) ans^=d[i];简单粗暴
但其实还有一种更加精巧的办法
void ReBuild() { cnt=0; drep(i,60,0) if(d[i]) drep(j,i-1,0) if(d[i]&(1ll<<j)) d[i]^=d[j]; rep(i,0,60) if(d[i]) t[cnt++]=d[i]; }事实上，可以看出的是，\(ReBuild\)之后，每一个\(d[i]\)都不存在了与后面\(d[j]\)冲突的\(1\)
所以这其实也就是类似于高斯消元的思想
这样就保证了每个\(d[i]\)每个位上都不会有冲突并且满足一一对应的性质,可以直接进行按位贪心了
\[ \ \]
\[ \ \]
题意：给定一些数及其权值，求最大独立集的最大权值和
按权值排序，能取就取，贪心即可，这里我们给出简略证明策略正确性
假设保证权值递减，若当前集合中已有的数为\(a,b,c,d,e\),现加入\(x\)与\(a,b\)产生冲突，即\(a \ xor \ b \ xor \ x=0\)，这时取\(x\)一定不会更优
其实很显然，因为如果取了\(x\)，替换\(a,b\)中的一个，此时仍能由异或产生\(a,b,x\)中的任意一个，总体上独立集的性质并未发生改变，但总权值减少了
证毕
int n; ll d[N]; pair <int,ll> P[N]; bool Ins(ll x){ drep(i,60,0) if(x&(1ll<<i)) { if(d[i]) x^=d[i]; else { d[i]=x; break; } } return x>0;//判断是否产生冲突 } int main(){ rep(i,1,n=rd()) scanf("%lld%d",&P[i].second,&P[i].first); sort(P+1,P+n+1); int ans=0; drep(i,n,1) if(Ins(P[i].second)) ans+=P[i].first; printf("%lld\n",ans); }\[ \ \]
\[ \ \]
讲这种应用之前我们先来细算不同异或和的个数:
设线性基元素的个数为cnt---->显然就是\(2^{cnt}\),即选或不选，且一定不会重复
这里的第k小是不同的异或答案情况下
这里我们先进行\(ReBuild\), 保证不冲突
然后,对于每一位的数(从小到大枚举),如果这一位存在着\(d[i]\),那么答案一定会是双倍于之前
将\(k\)按照二进制位分解后,对于每一位\(1\)取出答案异或即可
细节 :前面的定义里已经讲到,线性基的答案是异或不出\(0\)的,所以对于答案来说,如果存在\(0\)的情况,k要-1
(如何判断0?插入时返回的值就是)
ll d[70],t[70],cnt; bool Ins(ll x){ drep(i,60,0) if(x&(1ll<<i)) { if(d[i]) x^=d[i]; else d[i]=x; break; } } return x>0; } void ReBuild() { cnt=0; drep(i,60,0) if(d[i]) drep(j,i-1,0) if(d[i]&(1ll<<j)) d[i]^=d[j]; rep(i,0,60) if(d[i]) t[cnt++]=d[i];//将大于0的d[i]取出 } ll Work(ll k){ if(cnt<n) k--; if(k>=(1ll<<cnt)) return -1; ll res=0; rep(i,0,cnt-1) if(k&(1ll<<i)) res^=t[i];//按照二进制位取出 return res; } void Solve(){ memset(d,0,sizeof d); rep(i,1,n=rd()) Ins(rd()); ReBuild(); rep(ttt,1,rd()) printf("%lld\n",Work(rd())); }另解->可以不用\(ReBuild\)
直接在找答案时保证该有的位有1，不该有的位没有一就行了
ll Work(ll k){ if(cnt<n) k--; if(k>=(1ll<<cnt)) return -1; ll res=0; drep(i,cnt-1,0) { bool f1=(k&(1ll<<i)),f2=(res&(1ll<<p[i])); if(f1^f2) res^=t[i]; //f1^f2实际上是((f1&&!f2)||(!f1||f2)) } return res; } void Solve(){ memset(d,0,sizeof d); rep(i,1,n=rd()) Ins(rd()); cnt=0; rep(i,0,60) if(d[i]) p[cnt]=i,t[cnt++]=d[i]; rep(ttt,1,rd()) printf("%lld\n",Work(rd())); }\[\ \]
\[\ \]
至少要写了这道题，才算会了一点线性基
这题我们直接离线询问，思考，对于一段前缀\(a[\lbrace 1...r \rbrace ]\)的线性基，如何查询任意一个区间\(l_x,r\)的答案?
我们考虑线性基中的元素冲突时，应该取最大的一个，替换最小的一个，这样就保证了贡献的最优性，即可完成查询！
（仿佛很简单）
如何实现呢？我这里有一种暴力的做法
int d[30],t[30]; inline void Insert(int x,int id){ drep(i,20,0) if(x&(1<<i)) { if(d[i]) x^=d[i]; else { d[i]=x; t[i]=id; break; } } } int tmp[N]; inline void Ins(int x,int id){ int mi=1e9,p=-1; drep(i,20,0) if(x&(1<<i)) { if(d[i]) { x^=d[i]; if(t[i]<mi) mi=t[i],p=i; } else { d[i]=x,t[i]=id; break; } } int cnt=0; if(!x&&~p) t[p]=id; drep(j,20,0) if(d[j]) tmp[++cnt]=t[j],d[j]=0; sort(tmp+1,tmp+cnt+1,greater<int>()); rep(j,1,cnt) Insert(a[tmp[j]],tmp[j]); }是不是很暴力。。。
其实这个复杂度可以再优化，但是笔者就不多讲了
而且这个完全可以在线做的。。。
\[ \ \]
\[ \ \]
注意这题问的是1-n的路径
首先这题我们要想出一个性质
任何一条路径的异或值都可以随意地与任意多个环相接!!!
（自己理解一下，很简单）
所以就是处理出环值，插入线性基，对1-n路径的异或值跑最大值就好了。。。
int n,m; struct Edge{ int to,nxt; ll w; }e[E<<1]; int head[N],ecnt; void AddEdge(int u,int v,ll w){ e[++ecnt]=(Edge){v,head[u],w}; head[u]=ecnt; } #define erep(u,i) for(int i=head[u];i;i=e[i].nxt) int from[E],to[E]; ll len[E]; ll dis[N]; int vis[N]; void dfs(int u){ vis[u]=1; erep(u,i){ int v=e[i].to; if(vis[v]) continue; dis[v]=dis[u]^e[i].w; dfs(v); } } ll d[70]; bool Ins(ll x){ drep(i,60,0) if(x&(1ll<<i)) { if(d[i]) x^=d[i]; else { d[i]=x; return true; } } return false; } int main() { n=rd(),m=rd(); rep(i,1,m) { int u=rd(),v=rd(); ll w;scanf("%lld",&w); AddEdge(u,v,w); AddEdge(to[i]=v,from[i]=u,len[i]=w); } dfs(1); rep(i,1,m) Ins(len[i]^dis[from[i]]^dis[to[i]]); ll Ans=dis[n]; drep(i,60,0) if((Ans^d[i])>Ans) Ans^=d[i]; printf("%lld\n",Ans); }6.Xor-matic Number of the Graph-CodeForces - 724G
直接看我的另一篇题解吧
----->传送门
转载于:https://www.cnblogs.com/chasedeath/p/11276708.html
相关资源：JAVA上百实例源码以及开源项目