题目描述
给你一个无向图，有n个顶点和m条边，每条边上都有一个非负权值。
我们称一个三元组(u,v,s)是有趣的，当且仅当对于u,v,有一条从u到v的路径(可以经过相同的点和边多次)，其路径上的权值异或和为 s 。对于一条路径，如果一条边经过了多次，则计算异或和时也应计算多次。不难证明，这样的三元组是有限的。
计算所有有趣的三元组中s的和对于1e9+7的模数
题解
不知道线性基是什么东西的可以看看蒟蒻的
线性基神仙题
首先异或和肯定得用线性基
然后路径肯定得找出所有环
那么先dfs一遍，找出到每个点的任意一条路径，然后把所有的环都给扔进线性基里面，
考虑接下来怎么做
经过深(kan)思(le)熟(ti)虑(jie)，我们发现每一个连通块里的所有点都要两两统计答案，那么我们要根据xor采取一个方法：二进制逐位统计
假设从大到小考虑第$k$位，此时所有点可以分为两类，第$k$位为0或第$k$位为1
先考虑两个点全0或全1的情况，这种情况下两个点异或起来第$k$位为0，对答案没有贡献，那么只有在线性基里存在第$k$位为1的数，异或上这两个点才能使其对答案有贡献
那么这个基必须选，然后剩下的基有$2^{cnt-1}$种选法（$cnt$为线性基里的元素个数），这一位对答案的贡献就是$2^{cnt-1}*2^{k}$
然后不同为0或1的情况同理，这个基必须不能选，剩下的基的选法如上
ps：我上面两个基必须选或不选只是打个比方，真正的意思是把这一个基拿出来，那么如果剩下的异或出来第$k$位是否为0，都能通过异或上这一个数使其第$k$位变为1（如果已经是1就不用异或了），所以剩下的数怎么组合都没有关系，方案数肯定是那么多
然后剩下的……看代码好了
1 //minamoto 2 #include3 #include 4 #include 5 #define ll long long 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline ll read(){10 #define num ch-'0'11 char ch;bool flag=0;ll res;12 while((ch=getc())>'9'||ch<'0')13 (ch=='-')&&(flag=true);14 for(res=num;(ch=getc())<='9'&&ch>='0';res=res*10+num);15 (flag)&&(res=-res);16 #undef num17 return res;18 }19 const int N=4e5+5,mod=1e9+7;20 ll ans;21 int n,m,top,cnt,cir,u,v;ll e;22 int head[N],q[N],ver[N<<2],Next[N<<2],tot;ll edge[N<<2];23 ll b[105],bin[105],circle[N],dis[N],dig[2];24 inline void add(int u,int v,ll e){25 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;26 }27 void dfs(int u,int fa,ll d){28 dis[u]=d,q[++top]=u;29 for(int i=head[u];i;i=Next[i]){30 int v=ver[i];31 if(v!=fa){32 if(dis[v]==-1) dfs(v,u,dis[u]^edge[i]);33 else circle[++cir]=dis[u]^dis[v]^edge[i]; 34 }35 }36 }37 inline void insert(ll x){38 for(int i=63;i>=0;--i)39 if(x>>i&1){40 if(!b[i]) return (void)(b[i]=x,++cnt);41 x^=b[i];42 }43 }44 void init(){45 memset(b,0,sizeof(b)),cnt=0;46 for(int i=1;i<=cir;++i) insert(circle[i]);47 }48 void calc(){49 init();50 for(int j=0;j<=63;++j){51 bool flag=0;dig[0]=dig[1]=0;52 for(int i=1;i<=top;++i) dig[dis[q[i]]>>j&1]++;53 for(int i=0;i<=63;++i)54 if(b[i]>>j&1){flag=1;break;}55 ll res;56 if(flag){57 res=(dig[0]*(dig[0]-1)/2+dig[1]*(dig[1]-1)/2)%mod;58 if(cnt) (res*=bin[cnt-1])%=mod;59 (res*=bin[j])%=mod;60 (ans+=res)%=mod;61 }62 res=dig[0]*dig[1]%mod;63 if(flag){ if(cnt) (res*=bin[cnt-1])%=mod;}64 else (res*=bin[cnt])%=mod;65 (res*=bin[j])%=mod;66 (ans+=res)%=mod;67 }68 }69 int main(){70 // freopen("testdata.in","r",stdin);71 memset(dis,-1,sizeof(dis));72 bin[0]=1;for(int i=1;i<=63;++i) bin[i]=(bin[i-1]<<1)%mod;73 n=read(),m=read();74 for(int i=1;i<=m;++i){75 u=read(),v=read(),e=read();76 add(u,v,e),add(v,u,e);77 }78 for(int i=1;i<=n;++i)79 if(dis[i]==-1)80 top=cir=0,dfs(i,0,0),calc();81 printf("%lld\n",ans);82 return 0;83 }