题解 CF724G 【Xor-matic Number of the Graph】

小粉兔 · 2019-01-27 16:14:12 · 题解

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/CF724G.html。

题目传送门：CF724G。

题意简述：

一张 n 个点的无向图，边有边权。

定义三元组 (u,v,w)(1\le u < v\le n) 合法当且仅当存在从点 u 到点 v 存在一条边权异或和为 w 的路径，经过多次的边需要算多次。

求所有合法三元组的 w 值之和对 10^9+7 取模的值。

题解：

比较简单的线性基和图结合的题目，需要用到线性基的一些基本性质。

对异或线性基在图上的应用稍有了解的同学很快可以发现结论：

• 对于连通无向图 G=(V,E) 以及 G 的一棵生成树 T：
• 点 u 到点 v 所有路径的异或和可以被 T 中 u 到 v 的路径的异或和异或上线性基 B 表示出来。
• 更进一步地，T 中 u 到 v 的路径的异或和等于 u 到根的路径的异或和异或 v 到根的路径的异或和。
• 所以 u 到 v 所有路径的异或和等于 d_u\oplus d_v\oplus B，其中 d_x 表示 x 到根的路径的异或和。

对于一对 (u,v)，尝试统计 d_u\oplus d_v\oplus B 中所有数的和。

直接做并不是很好做，考虑按位分开做：

• 对于线性基 B 和二进制位 w，有结论：
• 设 B 中元素个数为 S，则 B 可以表示出 2^S 个不同的数。
• 如果 B 中存在二进制第 w 位为 1 的数，则那 2^S 个数中恰有 2^{S-1} 个数的二进制第 w 位为 1，另外 2^{S-1} 个数的二进制第 w 位为 0。
• 如果 B 中不存在二进制第 w 位为 1 的数，显然不可能表示出二进制第 w 位为 1 的数，全部 2^S 个数的二进制第 w 位均为 0。
  可以通过组合恒等式 \sum_{i=0}^{n}\binom{n}{i}[i\bmod 2=1]=\begin{cases}0&,n=0\\2^{n-1}&,n>0\end{cases} 证明。

统计每一位有多少种能被表示出来的方式，统计进答案即可。

这样需要枚举 (u,v)，其实很简单就能优化。

直接枚举二进制位 w，考虑线性基 B 中是否存在二进制第 w 位为 1 的数。

如果存在，这意味着无论 d_u,d_v 的二进制第 w 位是否为 1，都恰有 2^{S-1} 条使得异或和的二进制第 w 位为 1 的路径。
这意味着 u,v 可以随便选，对答案的贡献为 2^w2^{S-1}\binom{n}{2}。

如果不存在，这意味着 d_u,d_v 的二进制第 w 位必须恰有一个为 1，并且此时存在 2^S 条使得异或和的二进制第 w 位为 1 的路径。
这意味着 d_u,d_v 的第 w 位必须恰有一个为 1，记第 w 位为 1 的 d_x 的个数为 x，对答案的贡献为 2^w2^Sx(n-x)。

最后注意原图不一定联通，对于每个联通块分别计算即可。

时间复杂度 \mathrm{O}(n\log^2t_i)。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 100005;
const int MM = 400005;

int N, M;
int h[MN], nxt[MM], to[MM], tot; LL w[MM];
inline void ins(int x, int y, LL z) { nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot; }

LL B[60]; int C;
inline void Add(LL x) {
    for (int j = 59; ~j; --j) if (x >> j & 1)
        if (!B[j]) { B[j] = x, ++C; break; }
        else x ^= B[j];
}

bool vis[MN];
LL d[MN];
int s[MN], t;

void DFS(int u, LL v) {
    vis[u] = 1, d[u] = v, s[++t] = u;
    for (int i = h[u]; i; i = nxt[i]) {
        if (vis[to[i]]) Add(v ^ d[to[i]] ^ w[i]);
        else DFS(to[i], v ^ w[i]);
    }
}

LL Ans;

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i) {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        ins(x, y, z); ins(y, x, z);
    }
    for (int i = 1; i <= N; ++i) if (!vis[i]) {
        memset(B, 0, sizeof B), C = t = 0;
        DFS(i, 0);
        for (int j = 0; j < 60; ++j) {
            LL c = (1ll << j) % Mod;
            bool ok = 0;
            for (int k = 0; k < 60; ++k) if (B[k] >> j & 1) ok = 1;
            if (ok) Ans = (Ans + (LL)t * (t - 1) / 2 % Mod * ((1ll << C - 1) % Mod) % Mod * c) % Mod;
            else {
                int x = 0;
                for (int i = 1; i <= t; ++i) if (d[s[i]] >> j & 1) ++x;
                Ans = (Ans + (LL)x * (t - x) % Mod * ((1ll << C) % Mod) % Mod * c) % Mod;
            }
        }
    }
    printf("%d\n", (LL)Ans % Mod);
    return 0;
}