J 生成树计数 + 拆位

题意

给你一个带边权的无向图 $G$，他有 $n$ 个点，$m$条边。图函数 $F(G) = \bigwedge \limits_{i=1}^{m}e_i$，其中 $\bigwedge$ 表示按位与。

随机取 $G$ 的一个生成树 $T$，问你 $F(T)$ 的期望是多少。

思路

设 $G$ 的生成树 $T$ 的个数为 $D(G)$，那么期望为

$E(F(T)) = \frac{1}{D(G)}\sum \limits_{i=1}^{D(G)} F(T_i)$

直接计算的复杂度相当高。我们不妨将每个 $e_i$ 分解为二进制形式：

$F(G) = \bigwedge \limits_{j=1}^{m}(\sum \limits_{i=0}^{30} 2^ie_{ij})$ $=\sum \limits_{i=0}^{30} 2^i(\bigwedge \limits_{j=1}^{m}e_{ij})$ $=\sum \limits_{i=0}^{30} 2^i \times [G$ 中所有的 $e_{ij}=1]$

那么：

$E(F(T)) = \frac{1}{D(G)} \sum \limits_{i=1}^{D(G)}\sum \limits_{j=1}^{30}2^j \times [T_i$ 中所有的 $e_{ji}=1]$

$=\frac{1}{D(G)} \sum \limits_{j=1}^{30}2^j\sum \limits_{i=1}^{D(G)} [T_i$ 中所有的 $e_{ji}=1]$

$=\frac{1}{D(G)} \sum \limits_{j=1}^{30}2^jD(G$ 仅包含 $e_{ji}=1$ 的边$)$

而 $D(G)$ 可以使用矩阵树定理，通过计算基尔霍夫矩阵的 $N-1$ 阶主子式的行列式得到答案，计算一次 $D(G)$ 的时间复杂度为 $O(n^3)$, 总的时间复杂度为 $O(n^3\log n)$。注意重边。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using edge = pair<int, int>;

const int N = 205, MOD = 998244353;
ll a[N][N];
vector<edge> g[N];

ll quick_pow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}

ll det(int n) {
    ll ans = 1;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int j = i; j < n && u == -1; ++j)
            if (a[j][i] != 0) u = j;
        if (u == -1) return 0;

        if (i != u) ans = -ans;
        ans = (ans * a[u][u]) % MOD;
        std::swap(a[i], a[u]);

        a[i][i] = quick_pow(a[i][i], MOD - 2);
        for (int j = n - 1; j >= i; --j)
            a[i][j] = (a[i][j] * a[i][i]) % MOD;

        for (int j = 0; j < n; ++j) {
            if (i == j || a[j][i] == 0) continue;
            for (int k = n - 1; k >= i; --k)
                a[j][k] = (a[j][k] - a[j][i] * a[i][k]) % MOD;
        }
    }
    return ans;
}

ll matrix_tree(int n, int shift = 0, int mask = -1) {
    memset(a, 0, sizeof(a));

    for (int u = 0; u < n; ++u) {
        for (auto &&e: g[u]) {
            int v = e.first, w = e.second;
            if ((w >> shift) & mask)
                --a[u][v], --a[v][u], ++a[u][u], ++a[v][v];
        }
    }
    return det(n - 1);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i)
            g[i].clear();

        for (int i = 0; i < m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w), --u, --v;
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }

        ll ans = 0;
        for (int i = 0; i <= 30; ++i)
            ans = (ans + (1LL << i) * matrix_tree(n, i, 1)) % MOD;
        ans = ans * quick_pow(matrix_tree(n), MOD - 2) % MOD;
        printf("%lld\n", (ans + MOD) % MOD);
    }
    return 0;
}