【题目】
CF
给定一幅带边权无向图，定义一个三元组 ( u , v , w ) (u,v,w) (u,v,w)是有趣的，当且仅当存在一条 u u u到 v v v的路径（可以非简单），满足路径异或值为 w w w。
求所有有趣三元组 w w w之和。
n , m ≤ 2 × 1 0 5 , w ≤ 1 0 18 n,m\leq 2\times 10^5,w\leq 10^{18} n,m≤2×105,w≤1018
【解题思路】
首先求出一棵 DFS \text{DFS} DFS树，将所有环的权丢进线性基，那一条路径 ( u , v ) (u,v) (u,v)的可行权就是两点到根距离异或值再异或上任意个环的权值。
考虑对每一位分开计算，设线性基大小为 S S S。那么若线性基中某一位有 1 1 1，显然这一位不论 u , v u,v u,v怎么取都能有贡献，因此就是 ( n 2 ) ? 2 k ? 2 S ? 1 {n\choose 2}\cdot 2^k\cdot 2^{S-1} (2n?)?2k?2S?1。而若没有 1 1 1，则需要路径这一位为 0 0 0和 1 1 1的两个组合，那么答案就是 c n t ? 2 k ? 2 S cnt\cdot 2^k\cdot 2^S cnt?2k?2S。
【【线性基】CF724G Xor-matic Number of the Graph】【参考代码】
#include
using namespace std;
typedef long long ll;
const int N=1e5+10,M=61,mod=1e9+7;
ll read()
{
ll ret=0;
char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
return ret;
}namespace Math
{
ll fc[M],pw[M];
ll C(ll x){return x*(x-1)/2%mod;
}
void init(){fc[0]=pw[0]=1;
for(int i=1;
i 
