Expectation(生成树计数)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6836

题意:给你 n 个点 m 条边的图,按照输入顺序第 i 条边的权值为 2^i,生成树的权值为树上所有边的权值的二进制与运算,随机选择一颗生成树,求生成树权值的期望。

Input

The first line is an integer t(1t10), the number of test cases.
For each test case, there are two space-separated integers n(2n100) and m(1m104) in the first line, the number of nodes and the number of edges.
Then follows m lines, each contains three integers u,v,w(1u,v,n,1w109,uv), space separated, denoting an weight edge between u and v has weight w.

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(生成树计数)

原文地址:https://www.cnblogs.com/lsl127/p/13449644.html