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

智能推荐

ActiveMQ学习4-ActiveMQ的安全机制和集群模式

ActiveMQ的安全机制和集群模式 20 ActiveMQ安全机制 20.1 Web 控制台安全 20.2 消息服务器Broker安全 21 ActiveMQ主从集群 21.1 使用集群的重要性 20.2 主从集群的方式 20.2.1 shared filesystem Master-Slave方式主从集群 20.2.2 shared database Master-Slave方式主从集群 20...

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

猜你喜欢

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...