矩阵树定理（求生成树个数）

左手的ㄟ右手 2022-11-25 04:20 173阅读 0赞

2020hdu第6场？ 被这题卡的死死的，给你一个图每边有边权，一个树的权值为每边按位与，求生成树权值期望

get新知识点——矩阵树定理，简单来说就是把图化为矩阵，然后高斯消元，对角线乘积为生成树个数（我就存个板子，下次遇到不久会写了么，这知识点又不难）

高斯消元：n个未知量，至少需要n个线性无关的方程才有解，学完线代，知道可以化为增广矩阵，然后化为矩阵行列式，一位位带过去即可

矩阵树知识点链接：[https://blog.csdn.net/dazha6157/article/details/101894112][https_blog.csdn.net_dazha6157_article_details_101894112]

高斯消元链接：[https://blog.csdn.net/pengwill97/article/details/77200372][https_blog.csdn.net_pengwill97_article_details_77200372]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod=998244353;
    const int N=207;
    vector<pair<int,int> >son[N];
    ll mat[N][N];
    int n,m;
    ll qpow(ll a,ll b)
    {
        ll ans=1;
        while (b){
            if (b&1) ans=ans*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }
    ll guass()
    {
        ll ans=1;
        for (int i=2; i<=n; i++){
            for (int j=i+1; j<=n; j++)
                while (mat[j][i]){
                    ll p=mat[i][i]/mat[j][i];
                    for (int k=i; k<=n; k++)
                        mat[i][k]=(mat[i][k]-mat[j][k]*p%mod+mod)%mod;
                    swap(mat[i],mat[j]);
                    ans=-ans;
                }
            ans=ans*mat[i][i]%mod;
        }
        return (ans+mod)%mod;
    }
    
    int main()
    {
    
        int zs;
        scanf ("%d",&zs);
        while (zs--){
            scanf ("%d%d",&n,&m);
            for (int i=1; i<=n; i++) son[i].clear();
            memset(mat,0,sizeof mat);
            for (int i=1; i<=m; i++){
                int u,v,w;
                scanf ("%d%d%d",&u,&v,&w);
                son[u].push_back(make_pair(v,w));
                //son[v].push_back(make_pair(u,w));
                mat[u][v]--; mat[v][u]--;
                mat[u][u]++; mat[v][v]++;
            }
            ll ans=qpow(guass(),mod-2);
            ll fz=0;
            for (int wei=0; wei<=30; wei++){
                memset(mat,0,sizeof mat);
                for (int i=1; i<=n; i++)
                    for(int j=0;j<son[i].size();j++){
                   int x=son[i][j].second;
                   int k=son[i][j].first;
                            if (x&(1<<wei)){
                                mat[i][k]--; mat[k][i]--;
                                mat[i][i]++; mat[k][k]++;
                            }
                        }
    
                fz=(fz+qpow(2,wei)*guass()%mod)%mod;
            }
            
            
            printf("%lld\n",ans*fz%mod);
        }
        return 0;
    }

，

[https_blog.csdn.net_dazha6157_article_details_101894112]: https://blog.csdn.net/dazha6157/article/details/101894112
[https_blog.csdn.net_pengwill97_article_details_77200372]: https://blog.csdn.net/pengwill97/article/details/77200372