矩阵树 2020 Multi-University Training Contest 6 Expectation
题目大意：
给你一张n个点m条边的图，定义一个最小生成树的权值是所有边相与的结果，现在你随机选一个最小生成树，计算期望的权值，答案对998244353取模。
题解：
分析题目：
- 这个期望等于概率乘以权值，每一张图出现的概率可以算出来，所以现在只要求所有可能的权值之和即可。
- 求一张图所有最小生成树，一般用矩阵树来写，所以考虑怎么建树，达到题目的要求。
- 这个题目要求最小生成树的权值相与，那么可以考虑把权值拆开成二进制，1e9，最多32位，所以对于每一位，答案就是最小生成树的个数乘以一个(2^x) 。
#include <bits/stdc++.h>
#define debug(x) cout<<"debug:"<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long ll;
const int maxn = 110;
const int mod = 998244353;
ll K[maxn][maxn];
ll Gauss(int n){//求矩阵K的n-1阶顺序主子式
ll res=1;
for(int i=1;i<=n-1;i++){//枚举主对角线上第i个元素
for(int j=i+1;j<=n-1;j++){//枚举剩下的行
while(K[j][i]){//辗转相除
ll t=K[i][i]/K[j][i];
for(int k=i;k<=n-1;k++)//转为倒三角
K[i][k]=(K[i][k]-t*K[j][k]+mod)%mod;
swap(K[i],K[j]);//交换i、j两行
res=-res;//取负
}
}
res=(res*K[i][i])%mod;
}
return (res+mod)%mod;
}
struct node{
int u,v;
int bit[40];
}e[10010];
ll p[40];
void init() {
p[0] = 1;
for (int i = 1; i < 40; i++) p[i] = p[i - 1] * 2 % mod;
}
long long inv(long long x,long long mod) {
x %= mod;
long long k = mod - 2, ans = 1;
while (k) {
if (k & 1) ans = ans * x % mod;
x = x * x % mod;
k >>= 1;
}
return ans;
}
int main() {
int T;
init();
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
memset(K, 0, sizeof(K));
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[i].u = u, e[i].v = v;
K[u][u]++, K[v][v]++;
K[u][v]--, K[v][u]--;
for (ll j = 32; j >= 0; j--) {
int x = (1ll << j) & w;
e[i].bit[j] = x;
}
}
ll ans = 0;
ll num = inv(Gauss(n), mod);
for (ll i = 0; i <= 32; i++) {
memset(K, 0, sizeof(K));
for (int j = 1; j <= m; j++) {
if (e[j].bit[i] == 0) continue;
int u = e[j].u, v = e[j].v;
if (u == v) continue;
K[u][u]++, K[v][v]++;
K[u][v]--, K[v][u]--;
}
ans = (ans + Gauss(n) * p[i] % mod) % mod;
}
ans = ans * num % mod;
printf("%lld
", ans);
}
return 0;
}