【CF724G】Xor-matic Number of the Graph

题目

题目链接：https://codeforces.com/problemset/problem/724/G
给你一个无向图，有 (n) 个顶点和 (m) 条边，每条边上都有一个非负权值。
我们称一个三元组 ((u,v,s)) 是有趣的，当且仅当对于 (u,vin [1,n]) ，有一条从 (u) 到 (v) 的路径(可以经过相同的点和边多次)，其路径上的权值异或和为 (s) 。对于一条路径，如果一条边经过了多次，则计算异或和时也应计算多次。不难证明，这样的三元组是有限的。
计算所有有趣的三元组中 (s) 的和对于 (10^9+7) 的模数。
(nleq 10^5,mleq 2 imes 10^5, ext{边权}leq 10^{18})。

思路

把每一个连通块单独拎出来做。
我们知道，(x) 到 (y) 的任意一条路径异或和可以看作一条 (x) 到 (y) 的简单路径的异或和再异或上若干个环。那么随便找一棵现在处理的连通块的生成树，对于非树边，都可以与一些树边组合形成环。把这些环的异或和扔进线性基里。
发现每一位是互不影响的，考虑计算每一位的贡献。
对于第 (i) 位，假设存在一个环的第 (i) 位是 (1)，那么对于任意两个点，他们之间一定存在一条路径的第 (i) 位是一。此时线性基中除了第 (i) 位以外所有元素都可以选择，贡献就是

[inom{n}{2} imes 2^{ ext{siz}-1} imes 2^{i} ]

其中 ( ext{siz}) 是线性基大小。
如果不存在任意一个环的第 (i) 位是 (1)，我们记 ( ext{dis}_x) 表示该连通块生成树的根到 (x) 路径的异或和，那么只有 ( ext{dis}) 为 (0) 的和 ( ext{dis}) 为 (1) 的之间才能产生贡献，此时线性基中任意元素都可以选择，贡献为

[ ext{cnt}_i(n- ext{cnt}_i) imes 2^{ ext{siz}} imes 2^{i} ]

其中 ( ext{cnt}_i) 表示 ( ext{dis}) 第 (i) 位为 (1) 的数量。
时间复杂度 (O((n+m)log a))。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=400010,LG=60,MOD=1e9+7;
int n,m,tot,head[N],cnt[LG+1];
ll ans,dis[N];
bool vis[N];

struct VectorSpace
{
	int siz;
	ll c[LG+1];
	bool flag[LG+1];
	
	void ins(ll x)
	{
		if (!x) return;
		for (int i=0;i<=LG;i++)
			if (x&(1LL<<i)) flag[i]=1;
		for (int i=LG;i>=0;i--)
			if (x&(1LL<<i))
			{
				if (!c[i]) { c[i]=x; siz++; break; }
				x^=c[i];
			}
	}
	
	void clr()
	{
		memset(flag,0,sizeof(flag));
		memset(c,0,sizeof(c));
		siz=0;
	}
}vs;

struct edge
{
	int next,to;
	ll dis;
}e[N];

void add(int from,int to,ll dis)
{
	e[++tot]=(edge){head[from],to,dis};
	head[from]=tot;
}

void dfs(int x,ll val)
{
	dis[x]=val; vis[x]=1; m++;
	for (int i=0;i<=LG;i++)
		if (val&(1LL<<i)) cnt[i]++;
	for (int i=head[x];~i;i=e[i].next)
	{
		int v=e[i].to;
		if (!vis[v]) dfs(v,val^e[i].dis);
			else vs.ins(val^dis[v]^e[i].dis);
	}
}

int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		int x,y; ll z;
		scanf("%d%d",&x,&y);
		scanf("%lld",&z);
		add(x,y,z); add(y,x,z);
	}
	for (int i=1;i<=n;i++)
		if (!vis[i])
		{
			memset(cnt,0,sizeof(cnt));
			vs.clr(); m=0;
			dfs(i,0);
			for (int i=0;i<=LG;i++)
				if (vs.flag[i])
					ans=(ans+(1LL*m*(m-1)/2%MOD)*((1LL<<vs.siz-1)%MOD)%MOD*((1LL<<i)%MOD))%MOD;
				else
					ans=(ans+(1LL*cnt[i]*(m-cnt[i])%MOD)*((1LL<<vs.siz)%MOD)%MOD*((1LL<<i)%MOD))%MOD;
		}
	printf("%lld",ans);
	return 0;
}