题目大意：有一张$n$个点$m$条边的无向图，定义三元组$(u,v,s)$是有趣的，当且仅当有一条$u o v$的路径，路径上所有边的异或和为$s$。问所有有趣的三元组的$s$之和。$nleqslant10^5,mleqslant2 imes10^5,wleqslant10^{18}$
题解：可知，$u,v$之间路径可能的异或和为任意一条$u->v$的路径再异或上若干个环。先$dfs$求出图中所有环，丢进线性基。令$dis[u]$为任意一条$1 o u$的路径异或和，$ans=sumlimits_{i=1}^{n}sumlimits_{j=i+1}^ns(dis[i]oplus dis[j])$，$s(x)$表示$x$异或上若干线性基中的元素的和。而这可以通过枚举每一位的$01$来在$log_2n$的时间复杂度内求出。
若现在考虑到了第$i$位，$dis$中第$i$位有$d_0$个是$0$，$d_1$个是$1$，线性基中有$m$个元素，这$m$个元素第$i$位有$b_0$个是$0$，$b_1$个是$1$。
- $dis$异或出的第$i$位为$1$，有$d_0 imes d_1$种方法，那么线性基中异或出来要是$0$，若$b_1=0$，线性基的方案数是$2^m$，否则为$2^{m-1}$
- $dis$异或出的第$i$位为$0$，有$dbinom{d_0}2+dbinom{d_1}2$种方法，那么线性基中异或出来的要是$1$，若$b_1=0$，方案数为$0$，否则为$2^{m-1}$
卡点：现在$codeforces$网址有问题，没有交，不能保证代码的正确性
C++ Code：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define mul(a, b) (static_cast<long long> (a) * (b) % mod)
#define mul_(a, b) (static_cast<long long> (a) * (b))
const int maxn = 1e5 + 10, maxm = 2e5 + 10, mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
const int M = 63;
int dnum[M + 1][2], bnum[M + 1][2], num;
long long P[M + 1];
void insert(long long x) {
for (int i = M; ~i; --i) if (x >> i & 1)
if (P[i]) x ^= P[i];
else { P[i] = x, ++num; return ; }
}
int head[maxn], cnt;
struct Edge {
int to, nxt;
long long w;
} e[maxm << 1];
void addedge(int a, int b, long long c) {
e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;
e[++cnt] = (Edge) { a, head[b], c }; head[b] = cnt;
}
int n, m, ans, pw[maxn], q[maxn], tot;
long long dis[maxn];
bool vis[maxn];
void dfs(int u, long long w) {
dis[q[++tot] = u] = w, vis[u] = true;
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (!vis[v]) dfs(v, w ^ e[i].w);
else insert(w ^ dis[v] ^ e[i].w);
}
}
inline long long C2(int x) { return mul_(x, x - 1) / 2; }
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m; pw[0] = 1;
for (int i = 1; i <= n; ++i) reduce(pw[i] = pw[i - 1] + pw[i - 1] - mod);
for (int i = 0, x, y; i < m; ++i) {
static long long z;
std::cin >> x >> y >> z;
addedge(x, y, z);
}
for (int i = 1; i <= n; ++i) if (!vis[i]) {
tot = num = 0;
memset(P, 0, sizeof P);
memset(dnum, 0, sizeof dnum);
memset(bnum, 0, sizeof bnum);
dfs(i, 0);
for (int i = M; ~i; --i) if (P[i])
for (int j = M; ~j; --j) ++bnum[j][P[i] >> j & 1];
for (int i = 1; i <= tot; ++i)
for (int j = M; ~j; --j) ++dnum[j][dis[q[i]] >> j & 1];
for (int i = M; ~i; --i)
if (bnum[i][1])
ans = (ans + (mul_(dnum[i][0], dnum[i][1]) + C2(dnum[i][0]) + C2(dnum[i][1])) % mod * pw[num - 1] % mod * pw[i]) % mod;
else
ans = (ans + mul(dnum[i][0], dnum[i][1]) * pw[num] % mod * pw[i]) % mod;
}
std::cout << ans << '
';
return 0;
}