codeforces_724G Xor-matic Number of the Graph

题目:

  You are given an undirected graph, constisting of n vertices and m edges. Each edge of the graph has some non-negative integer written on it.
  Let's call a triple (u, v, s) interesting, if 1 ≤ u < v ≤ n and there is a path (possibly non-simple, i.e. it can visit the same vertices and edges multiple times) between vertices u and v such that xor of all numbers written on the edges of this path is equal to s. When we compute the value s for some path, each edge is counted in xor as many times, as it appear on this path. It's not hard to prove that there are finite number of such triples.
  Calculate the sum over modulo 10^9 + 7 of the values of s over all interesting triples.

思路:

  先考虑如何表达出两点之间所有路径的异或值。在整个图上随便找出一棵生成树,定义两点间的树上路径为基本路径,树边与一条非树边组成的环叫做基本环。根据 的性质可以发现,树上任意的路径都能由基本路径和基本环组成,且不同的基本环集合对应着不同的路径。
  所以现在要求的就是 为基本环子集的异或和)。
  分别考虑二进制每一位对答案的贡献。
  如果线性基 中存在第 位,那么一定能分别找出 个子集异或和存在或不存在第 位。那对于每一种基本路径都有 存在第 位。
  如果线性基 中不存在第 位,那第 位就来自基本路径,那路径的端点必须满足一个到根的异或值存在第 位,另一个不存在。这时环的选取就任意了。

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
typedef unsigned long long ull;
const int T = 63, N = 1e5 + 5, M = 2e5 + 5, MOD = 1e9 + 7;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
struct Edge {
    int to;
    ull val;
};
Link<N, M * 2, Edge> G;

ull lb[T + 5];
void insert(ull x) {
    drep(i, T, 0) {
        if(~x >> i & 1) continue;
        if(lb[i]) x ^= lb[i];
        else {
            rep(j, 0, i - 1) if(x >> j & 1) x ^= lb[j];
            rep(j, i + 1, T) if(lb[j] >> i & 1) lb[j] ^= x;
            lb[i] = x;
            break;
        }
    }
}

int dfn[N], cur, vec[N];
ull xsum[N];
void dfs(int o) {
    dfn[o] = ++cur; vec[cur] = o;
    erep(k, G, o) {
        int v = G[k].to;
        ull x = G[k].val;
        if(dfn[v]) {
            insert(x ^ xsum[v] ^ xsum[o]);
            continue;
        }
        xsum[v] = xsum[o] ^ x;
        dfs(v);
    }
}

int p2[T + 5]; // 2 ^ x

int main() {
    // freopen("data.in", "r", stdin);
    p2[0] = 1;
    rep(i, 1, T) p2[i] = (p2[i - 1] << 1) % MOD;
    int n, m;
    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        int a, b;
        ull x;
        scanf("%d%d%llu", &a, &b, &x);
        G.add(a, (Edge) {b, x});
        G.add(b, (Edge) {a, x});
    }
    int ans = 0;
    rep(i, 1, n) {
        int tmp = 0;
        if(dfn[i]) continue;
        memset(lb, 0, sizeof lb);
        cur = 0; dfs(i);
        int cnt = (ull) cur * (cur - 1) / 2 % MOD;
        rep(i, 0, T) tmp += (lb[i] != 0);
        rep(i, 0, T) {
            bool flag = false;
            rep(j, 0, T) flag |= (lb[j] >> i & 1);
            if(!flag) {
                int x = 0;
                rep(j, 1, cur) x += (xsum[vec[j]] >> i & 1);
                (ans += (ull) p2[i] * (cur - x) % MOD * x * p2[tmp] % MOD) %= MOD;
            }
            else (ans += (ull) p2[i] * p2[tmp - 1] % MOD * cnt % MOD) %= MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}