#### Expectation(生成树计数)

Input

The first line is an integer

Output

For each test case, output a single line with a single integer, denoting the answer.

Sample Input

1
3 3
1 2 1
1 3 1
2 3 1

Sample Output

1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;

typedef long long ll;

const int N = 110;
const double eps = 1e-8;
const ll mod = 998244353;

struct node {
int from, to;
ll w;
} edge[10010];

int n, m;
ll ka[N][N];
ll pow2[35];

ll gauss(int n) {
ll res = 1;
for(int i = 1; i <= n - 1; i++) {
for(int j = i + 1; j <= n - 1; j++) {
while(ka[j][i]) {
int t= ka[i][i] / ka[j][i];
for(int k = i; k <= n - 1; k++) {
ka[i][k] = (ka[i][k] - t * ka[j][k] + mod) % mod;
}
swap(ka[i], ka[j]);
res = -res;
}
}
res = (res * ka[i][i]) % mod;
}
return (res + mod) % mod;
}

ll qpow(ll a, ll n) {
ll ans = 1;
while(n) {
if(n & 1) ans = ans * a % mod;
a = a * a % mod;
n >>= 1;
}
return ans % mod;
}

ll inv(ll x) {
return qpow(x, mod - 2) % mod;
}

int main() {
pow2[0] = 1;
for(int i = 1; i < 35; i++) {
pow2[i] = pow2[i - 1] * 2;
}
int t;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
memset(ka, 0, sizeof(ka));
for(int i = 1; i <= m; i++) {
scanf("%d %d %lld", &edge[i].from, &edge[i].to, &edge[i].w);
int u = edge[i].from;
int v = edge[i].to;
ka[u][u]++;
ka[v][v]++;
ka[u][v]--;
ka[v][u]--;
}
ll tot = gauss(n);
ll fin = 0;
for(int bt = 0; bt <= 30; bt++) {
memset(ka, 0, sizeof(ka));
for(int i = 1; i <= m; i++) {
int u = edge[i].from;
int v = edge[i].to;
ll w = edge[i].w;
if(w & pow2[bt]) {
ka[u][u]++;
ka[v][v]++;
ka[u][v]--;
ka[v][u]--;
}
}
ll ans = gauss(n);
fin += pow2[bt] * ans % mod;
fin %= mod;
}
fin *= inv(tot);
fin %= mod;
printf("%lld
", fin);
}
return 0;
}
View Code

Expectation(生成树计数)