2020 Multi-University Training Contest 6 1010 Expectation（矩阵树定理）

题目

　　http://acm.hdu.edu.cn/showproblem.php?pid=6836

题意

　　求随机选出一个生成树的权值期望，权值为所有边按位与后的值。

题解

　　易知每一位对于答案的贡献是独立的，所以可以按位分别建图，用矩阵树定理求出生成树个数，第 i 位对答案的贡献也就是  * 生成树数量。

#include <bits/stdc++.h>
// #include <iostream>
// #include <cstring>
// #include <string>
// #include <algorithm>
// #include <cmath>
// #include <cstdio>
// #include <queue>
// #include <stack>
// #include <map>
// #include <bitset>
// #include <set>
// #include <vector>
// #include <iomanip>
#define ll long long
#define ull unsigned long long
#define met(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define bep(i, a, b) for(int i = a; i >= b; --i)
#define lowbit(x) (x&(-x))
#define MID (l + r) / 2
#define ls pos*2
#define rs pos*2+1
#define pb push_back
#define ios() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

const int maxn = 1e6 + 1010;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const double eps = 1e-6;
const double PI = acos(-1);

struct node {
    int u, v;
    int w;
}edge[maxn];

ll MAP[110][110];
int n, m;

ll qpow(ll x, ll n) {
    ll sum = 1;
    x %= mod;
    while(n) {
        if(n & 1) (sum *= x) %= mod;
        (x *= x) %= mod;
        n >>= 1;
    }
    return sum;
}
void get_matrix(int x) {
    rep(i, 1, n) {
        rep(j, 1, n) {
            MAP[i][j] = 0;
        }
    }
    rep(i, 1, m) {
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        if(((w >> x) & 1) == 1) {
            MAP[u][u]++;
            MAP[v][v]++;
            MAP[u][v]--;
            MAP[v][u]--;
        }
    }
}
ll calc_matrix() {
    ll sum = 1;
    rep(i, 1, n - 1) {
        // rep(j, i, n - 1) {
        //     if(MAP[i][j]) {
        //         if(i != j) swap(MAP[i], MAP[j]);
        //         break;
        //     }
        // }
        sum = sum*MAP[i][i] % mod;
        rep(j, i + 1, n - 1) {  
            ll t = MAP[j][i] * qpow(MAP[i][i], mod - 2) % mod;
            rep(k, i, n - 1) {
                MAP[j][k] = ((MAP[j][k] - t * MAP[i][k] % mod) % mod + mod) % mod;
            }
        }
    }
    return (sum % mod + mod) % mod;
}

int main() {
    ios();
    int T;
    cin >> T;
    while(T--) {
        cin >> n >> m;
        rep(i, 1, n) {
            rep(j, 1, n) {
                MAP[i][j] = 0;
            }
        }
        rep(i, 1, m) {
            cin >> edge[i].u >> edge[i].v >> edge[i].w;
            MAP[edge[i].u][edge[i].u]++;
            MAP[edge[i].v][edge[i].v]++;
            MAP[edge[i].u][edge[i].v]--;
            MAP[edge[i].v][edge[i].u]--;
        }
        ll tot = calc_matrix();
        ll sum = 0;
        rep(i, 0, 30) {
            get_matrix(i);
            sum = (sum + (1ll << i) % mod * calc_matrix() % mod) % mod;
        }
        cout << qpow(tot, mod - 2) * sum % mod << endl;
    }
    return 0;
}