线性基棒题
建议做这题前先看看线性基的概念，然后A掉这道题--->路径最大异或和
这两个题都用到了一个相同的性质：
任何一条路径的异或值都可以随意地与任意多个环相接
对于这道题来说，每一条路径都有它独立的贡献，并且都需要和每一个异或和不同的环相接
处理环异或和不同自然使用线性基判断插入是否成功
所以是一个全局统计的题目
如何统计？
将所有点到根节点的异或前缀和存下来，相互之间异或，就得到了所有路径的异或值，然后再添加环就很简单了
如何存呢？当然是按位算贡献
详见代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define reg register #define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i) #define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i) char IO; inline int rd(){ int s=0,f=0; while(!isdigit(IO=getchar())) if(IO=='-') f=1; do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return f?-s:s; } const int N=5e5+10,E=2e5+10,P=1e9+7; 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) ll dis[N]; int vis[N]; int cnt[70][2]; ll tmp[70][2]; vector <int> Points; vector <ll> cir; void dfs(int u){ Points.push_back(u); rep(i,0,60) if(dis[u]&(1ll<<i)) cnt[i][1]++; else cnt[i][0]++; vis[u]=1; erep(u,i) { int v=e[i].to; if(vis[v]) { cir.push_back(dis[v]^dis[u]^e[i].w);//说明这条边在一个环上 continue; } dis[v]=dis[u]^e[i].w; dfs(v); } } ll Ans; ll d[70]; bool Ins(ll d[],ll x){ drep(i,60,0) if(x&(1ll<<i)) { if(d[i]) x^=d[i]; else { d[i]=x; return true; } } return false; }//线性基 void Solve(int rt){ Points.clear();cir.clear(); memset(cnt,0,sizeof cnt);memset(d,0,sizeof d); memset(tmp,0,sizeof tmp); dfs(rt); rep(k,0,(int)Points.size()-1) { ll t=dis[Points[k]]; rep(i,0,60) if(t&(1ll<<i)) cnt[i][1]--; else cnt[i][0]--; rep(i,0,60) { if(t&(1ll<<i)) tmp[i][0]+=cnt[i][1],tmp[i][1]+=cnt[i][0]; else tmp[i][0]+=cnt[i][0],tmp[i][1]+=cnt[i][1]; tmp[i][0]%=P,tmp[i][1]%=P;//依次与其他点形成贡献 } rep(i,0,60) if(t&(1ll<<i)) cnt[i][1]++; else cnt[i][0]++; } rep(i,0,(int)cir.size()-1) {//加入环 ll t=cir[i]; if(!Ins(d,t)) continue; rep(i,0,60) { if(t&(1ll<<i)) { ll t=(tmp[i][0]+tmp[i][1])%P; tmp[i][0]=tmp[i][1]=t; } else tmp[i][0]*=2,tmp[i][1]*=2; tmp[i][0]%=P,tmp[i][1]%=P; } } rep(i,0,60) { ll b=(1ll<<i)%P; (Ans+=tmp[i][1]%P*b%P)%=P; } } 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(v,u,w); } rep(i,1,n) if(!vis[i]) Solve(i);//图不保证联通 printf("%lld\n",Ans*500000004%P);//答案会被多算一次，所以乘上Inv(2,1e9+7) }转载于:https://www.cnblogs.com/chasedeath/p/11285489.html
相关资源：JAVA上百实例源码以及开源项目