[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;
     }