[Codeforces 724G. Xor-matic Number of the Graph]线性基+计数

分类：Data Structure bitmasks math

1. 题目链接

[Codeforces 724G. Xor-matic Number of the Graph]

2. 题意描述

一个边权非负整数的无向连通图，节点编号为$1$~$n$，三元组$\mathrm{<u,v,s>}$表示从$u$到$v$的路径的异或和为$s$（可以多次经过同一个顶点或同一条边），求出所有这样的三元组$\mathrm{<u,v,s>}$中关于$s$的和。
数据范围：$1 ≤ n ≤ 10000, 0 ≤ m ≤ 200 000,0≤边权≤10^{18}$

3. 解题思路

假设这个无向图是一棵树，那么可以通过对每个二进制位单独算贡献。统计出树上的边中，每一位出现的次数，令$a_j，b_j$分别表示第$j$位在树上出现了$a_j$次$\mathrm0$、$b_j$次$\mathrm1$，那么答案就是$\sum_{j=0}^{log_2(10^{18})}(a_j*b_j*2^j)$。
现在考虑这个无向图是一个联通图，那么就可能存在一些环。做法同《[BZOJ 2115 Wc2011 Xor]线性基》，求出所有环的异或值，然后求一次线性基。设线性基的秩为$r$。那么，按位统计答案的时候应该这样做：

1. 如果线性基中的第$j$位全为0，那么贡献就是$\sum_{j=0}^{log_2(10^{18})}(a_j*b_j*2^j*2^r)$,即线性基的任意组合都是可以的。
   • 反之，那么贡献就是$\sum_{j=0}^{log_2(10^{18})}(a_j*b_j*2^j*2^{r-1}+\frac{a_j*(a_j-1)}{2}*2^{r-1}+\frac{b_j*(b_j-1)}{2}*2^{r-1})$，即根据选的两个点的路径上的异或值为0还是为1，决定线性基的该位选还是不选。

   • 感觉这道题目学到了很多姿势！

     4. 实现代码

     #include <bits/stdc++.h>
     using namespace std;
     
     typedef long long ll;
     typedef unsigned long long ull;
     typedef pair<int, int> pii;
     
     const int inf = 0x3f3f3f3f;
     const ull infl = 0x3f3f3f3f3f3f3f3fLL;
     template<typename T> inline void umax(T &a, T b) { a = max(a, b); }
     template<typename T> inline void umin(T &a, T b) { a = min(a, b); }
     
     const int MAXN = 100005;
     const ull MOD = 1e9 + 7;
     
     typedef pair<int, ull> Edge;
     vector<Edge> G[MAXN];
     int n, m;
     vector<ull> xorv;
     ull xpath[MAXN], base[100], qz[200];
     bool used[MAXN];
     int cnt[100][2];
     
     void dfs(int u, int fa) {
         int v; ull w;
         used[u] = true;
         for (int i = 0; i < G[u].size(); ++i) {
             tie(v, w) = G[u][i];
             if (v == fa) continue;
             if (used[v]) {
                 xorv.push_back(xpath[v] ^ xpath[u] ^ w);
             } else {
                 xpath[v] = xpath[u] ^ w;
                 dfs(v, u);
             }
         }
         for (int j = 0; j <= 62; ++j) {
             ++ cnt[j][xpath[u] >> j & 1];
         }
     }
     
     int Guass_base() {
         int rank = 0;
         for (int i = 0; i <= 62; ++i) base[i] = 0;
         for (int i = 0; i < xorv.size(); ++i) {
             for (int j = 62; j >= 0; --j) {
                 if (!(xorv[i] >> j & 1)) continue;
                 if (!base[j]) {
                     base[j] = xorv[i];
                     ++ rank;
                     break;
                 }
                 xorv[i] ^= base[j];
             }
         }
         return rank;
     }
     
     int main() {
     #ifdef ___LOCAL_WONZY___
         freopen("input.txt", "r", stdin);
     #endif // ___LOCAL_WONZY___
         int u, v; ull w;
         qz[0] = 1;
         for (int i = 1; i < 200; ++i) qz[i] = qz[i - 1] * 2 % MOD;
         while (~scanf("%d %d", &n, &m)) {
             for (int i = 1; i <= n; ++i) {
                 G[i].clear();
                 used[i] = false;
             }
             for (int i = 1; i <= m; ++i) {
                 scanf("%d %d %llu", &u, &v, &w);
                 G[u].push_back(Edge(v, w));
                 G[v].push_back(Edge(u, w));
             }
             ull ans = 0;
             for (int i = 1; i <= n; ++i) {
                 if (used[i]) continue;
                 xorv.clear();
                 memset(cnt, 0, sizeof(cnt));
                 dfs(i, 0);
                 sort(xorv.begin(), xorv.end());
                 xorv.erase(unique(xorv.begin(), xorv.end()), xorv.end());
                 reverse(xorv.begin(), xorv.end());
                 int rank = Guass_base();
                 for (int j = 0; j <= 62; ++j) {
                     bool sign = false;
                     for (int k = 0; k <= 62; ++k) sign |= (base[k] >> j & 1);
                     if (!sign) {
                         ull temp = (ull)cnt[j][0] * cnt[j][1];
                         ans = (ans + temp % MOD * qz[j + rank]) % MOD;
                     } else {
                         ull temp = (ull)cnt[j][0] * cnt[j][1];
                         temp += (ull)cnt[j][0] * (cnt[j][0] - 1) / 2;
                         temp += (ull)cnt[j][1] * (cnt[j][1] - 1) / 2;
                         ans = (ans + temp % MOD * qz[j + rank - 1]) % MOD;
                     }
                 }
             }
             printf("%llu\n", ans);
         }
     #ifdef ___LOCAL_WONZY___
         cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << "ms." << endl;
     #endif // ___LOCAL_WONZY___
         return 0;
     }