2020 Multi-University Training Contest 6---- HDU--6836、Expectation(矩阵树)

标签: 生成树

题目链接

题面:
在这里插入图片描述

题意:
一棵树的权值定义为这棵树所有的边权的 按位与 的值。
给定一张图,问这张图的一棵生成树的权值的期望。

题解:
由于 按位与 在这个题中每一位独立。我们可以拆位来看。
对于第 kk 位,我们把第 kk11 的边都拿出来组成一张新图,然后在这张新图上求解生成树的个数,那么这一位的贡献就是 (1<<k)cnt()cnt()(1<<k)*\frac{cnt(新图)}{cnt(原图)}

代码:

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x)  (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=210;
const int maxm=10000100;
const int maxp=100100;
const int up=30;

ll a[maxn][maxn];
struct node
{
    int x,y,z;
    node(){}
    node(int a,int b,int c)
    {
        x=a,y=b,z=c;
    }
};
vector<node>vc;
int n,m;

ll mypow(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 Gu(int n)
{
    ll res=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(a[j][i]!=0)
            {
                if(j!=i)
                {
                    res=-res;
                    for(int k=i;k<=n;k++)
                        swap(a[i][k],a[j][k]);
                }
                break;
            }
        }
        if(a[i][i]==0) return 0;
        res=res*a[i][i]%mod;

        ll inv=mypow(a[i][i],mod-2);
        for(int j=i+1;j<=n;j++)
        {
            int tmp=a[j][i]*inv%mod;
            for(int k=i;k<=n;k++)
                a[j][k]=(a[j][k]-tmp*a[i][k]%mod+mod)%mod;
        }
    }
    return abs(res);
}

ll get(int k,bool flag)
{
    memset(a,0,sizeof(a));
    int x,y;
    for(int i=0;i<vc.size();i++)
    {
        if(!flag||(vc[i].z>>k)&1)
        {
            x=vc[i].x,y=vc[i].y;
            a[x][x]=(a[x][x]+1)%mod;
            a[y][y]=(a[y][y]+1)%mod;
            a[x][y]=(a[x][y]-1+mod)%mod;
            a[y][x]=(a[y][x]-1+mod)%mod;
        }
    }
    return Gu(n);
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        vc.clear();
        int x,y,z;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            vc.pb(node(x,y,z));
        }
        ll sum=get(0,false);
        sum=mypow(sum,mod-2);
        ll ans=0;
        for(int i=30;i>=0;i--)
        {
            ans=(ans+get(i,true)*sum%mod*(1<<i)%mod)%mod;
        }
        printf("%lld\n",ans);
    }

    return 0;
}



版权声明:本文为zhaoxinxin1234原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zhaoxinxin1234/article/details/108274686

智能推荐

fluent-ffmpeg在electron框架中实现推流

需要准备这几个东西 electron框架 ffmpeg.exe应用程序 链接:https://pan.baidu.com/s/1TyzYlWG0p7cxpqrzziVRCA  提取码:ofd2(也可自行去官网下载) fluent-ffmpeg插件 一个rtmp流地址 首先要做以下几步操作 1.将ffmpeg.exe文件放到electron项目文件夹中 2.安装插件和electron框架并...

bireme数据源同步工具--debezium+kafka+bireme

1、介绍 Bireme 是一个 Greenplum / HashData 数据仓库的增量同步工具。目前支持 MySQL、PostgreSQL 和 MongoDB 数据源 官方介绍文档:https://github.com/HashDataInc/bireme/blob/master/README_zh-cn.md 1、数据流 Bireme 采用 DELETE + COPY 的方式,将数据源的修改记...

一致性hash算法

散列(hash)在我看来就是一个数组,而与数组不同的点在于数组是按顺序写入的,而hash是按照一定的hash算法确定元素在数组中的位置的。hash最难的问题在于会有冲突出现,如果两个object根据相应的hash算法得出的值一样便产生了hash冲突。在所有解决hash冲突的方法中,我最欣赏的是链式解决法,即将hash到同一位置的元素用链表连接。当然还有其它几种处理hash冲突的算法,比如建立公共溢...

OpenCV-Python learning-1.安装,图片读取显示

1. OpenCV与OpenGL区别 https://www.zhihu.com/question/20212016 一个是让机器识别东西的,OpenCV是给电脑做眼睛的。 一个是让机器计算出更好画面的,OpenGL用在游戏渲染方面很多。 OpenCV(Open Source Computer Vision Library)是一个基于(开源)发行的跨平台计算机视觉库,OpenGL(全写Open G...

Mycat+Mysql分布式架构改造和性能压力测试

架构实现 Mycat作为数据库高可用中间件具备很多的功能,如负载均衡,分库分表,读写分离,故障迁移等。结合项目的实际情况,分库分表功能对于关联查询有很高的要求,需要从业务角度考虑分库分表后的关联查询SQL的分析,业务代码动作较大,所以在此方案中我们不考虑分库分表。主要应用Mycat的负载均衡及故障迁移的功能即可。 整个架构改造包括两个部分,第一是单例Mysql改为多个Mysql,同时负载均衡,并且...

猜你喜欢

人脸识别之疲劳检测(二)阈值法、KNN分类和K-means聚类

Table of Contents 1、均值法 2、中值法 3、KNN 4、K-means 结合上一节在获得人眼特征点后需要对睁眼闭眼状态做出判断,方法的选择需要经验结合公平的评价方法,使用大量测试集得到不同方法下的精确度并做出比较: 1、均值法 50帧睁眼数据取均值,得到不同阈值下精确度。 2、中值法 50帧睁眼数据取中值,得到不同阈值下精确度。 3、KNN KNN是一种ML常用分类算法,通过测...

CodeForce Tic-Tac-Toe

Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules. The game is played on the foll...

Python雾里看花-抽象类ABC (abstract base class)

首先认识模块 abc,python中没有提供抽象类与抽象方法,然而提供了内置模块abc来模拟实现抽象类,例如提供泛映射类型的抽象类 abc.MutableMapping 继承abc.MutableMapping构造一个泛映射类型(类似python中的dict) 当然继承abc.Mapping 也可以,毕竟MutableMapping是其子类 dict是python中典型的映射类型数据结构,其接口的...

python 文件操作

2, with open (‘xx.txt’,‘w’,encoding=‘utf-8’) as f: f.write(‘文件内容或对象’)...

【Python基础】使用统计函数绘制简单图形

机器学习算法与自然语言处理出品 @公众号原创专栏作者 冯夏冲 学校 | 哈工大SCIR实验室在读博士生 2.1 函数bar 用于绘制柱状图 2.2 函数barh 用于绘制条形图 2.3 函数hist 用于绘制直方图 直方图与柱状图的区别 函数pie 用于绘制饼图 2.5 函数polor 用于绘制极线图 极线图是在极坐标系上绘出的一种图。在极坐标系中,要确定一个点,需要指明这个点距原点的角...