lessons/参考实现/10-高斯消元与CRT/CodeForces-724G.cpp

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

using ull = unsigned long long;
constexpr long long MOD = 1'000'000'007LL;
constexpr int BITS = 60;

struct LinearBasis {
    array<ull, BITS> pivot{};
    int rank = 0;
    void insert(ull value) {
        for (int bit = BITS - 1; bit >= 0; --bit) {
            if (((value >> bit) & 1ULL) == 0) continue;
            if (pivot[bit] == 0) {
                pivot[bit] = value;
                ++rank;
                return;
            }
            value ^= pivot[bit];
        }
    }
    bool varies(int bit) const {
        for (ull value : pivot) if ((value >> bit) & 1ULL) return true;
        return false;
    }
};

long long mod_power(long long base, int exponent) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent & 1) result = result * base % MOD;
        base = base * base % MOD;
        exponent >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    struct Edge { int to; ull weight; };
    vector<vector<Edge>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        ull w;
        cin >> u >> v >> w;
        --u; --v;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    vector<char> seen(n, false);
    vector<ull> potential(n, 0);
    long long answer = 0;
    for (int root = 0; root < n; ++root) {
        if (seen[root]) continue;
        vector<int> component;
        vector<int> stack{root};
        seen[root] = true;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            component.push_back(v);
            for (const Edge &edge : graph[v]) {
                if (!seen[edge.to]) {
                    seen[edge.to] = true;
                    potential[edge.to] = potential[v] ^ edge.weight;
                    stack.push_back(edge.to);
                }
            }
        }
        LinearBasis basis;
        for (int v : component) {
            for (const Edge &edge : graph[v]) {
                basis.insert(potential[v] ^ potential[edge.to] ^ edge.weight);
            }
        }
        long long combinations = mod_power(2, basis.rank);
        long long pairs = 1LL * component.size() * (component.size() - 1) / 2 % MOD;
        for (int bit = 0; bit < BITS; ++bit) {
            long long count;
            if (basis.varies(bit)) {
                count = pairs * mod_power(2, basis.rank - 1) % MOD;
            } else {
                long long ones = 0;
                for (int v : component) ones += (potential[v] >> bit) & 1ULL;
                count = ones % MOD * ((component.size() - ones) % MOD) % MOD;
                count = count * combinations % MOD;
            }
            answer = (answer + count * ((1ULL << bit) % MOD)) % MOD;
        }
    }
    cout << answer << '\n';
    return 0;
}