整体思想以及取模

前言:一开始由于失误,误以为分数相加取模不能,但是其实是可以取模的

这个题目如果按照一般方法,到达每个节点再进行概率统计,但是不知道为什么只过了百分之十五的测试集


题目地址
在这里插入图片描述

附上没过关的代码

#include<bits/stdc++.h>
using namespace std;#define int long longint n; int ans = 0;
const int N = (int)2e6 + 5;
const int Mod = 998244353;
int e[N], ne[N], h[N / 2], idx = 0;
void add(int a, int b) {e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}int qw(int x, int p) {int temp = 1;while (p) {if(p&1)temp = x * temp % Mod;x = x * x % Mod;p >>= 1;}return temp;
}void dfs(int u, int fa, int g, int step) {int cnt = 0;for (int i = h[u]; i; i = ne[i]) {int v = e[i]; if (fa == v) continue;cnt++;}if (cnt == 0) {// 已经是子节点了 //ans = (ans + (step % Mod) * qw(g, Mod - 2)) % Mod; return;ans = (ans + step*g%Mod) % Mod; return;}g = (g % Mod) * (qw(cnt, Mod - 2) % Mod) % Mod;for (int i = h[u]; i; i = ne[i]) {int v = e[i]; if (fa == v) continue;dfs(v, u, g , step + 1);}
}signed main() {cin >> n;for(int i=1;i<n;i++){int u,v; cin >> u >> v;add(u,v),add(v,u);}if(n==1){cout << 0 ; return 0;}dfs(1,0,1,0);cout << ans;return 0;
}

再写一个过关的,按照官方答案的解法的

#include<bits/stdc++.h>
using namespace std;#define int long longint n; int ans = 0;
const int N = (int)2e6 + 5;
const int Mod = 998244353;
const int P = 998244353;
int e[N], ne[N], h[N / 2], idx = 0;
vector<int> a[N / 2];
int siz[N], ye[N]; // 记录每一层的节点个数以及叶子节点的个数 
void add(int a, int b) {e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}int qw(int x, int p) {int temp = 1;while (p) {if (p & 1)temp = x * temp % Mod;x = x * x % Mod;p >>= 1;}return temp;
}void dfs(int u, int fa, int dep) {int cnt = 0; siz[dep]++;for (int i = h[u]; i; i = ne[i]) {int to = e[i]; if (to == fa) continue;cnt++; dfs(to, u, dep + 1);}if (cnt == 0) {ye[dep]++;}
}void solve() {int pre = 1; // 概率for (int i = 1; i < n; i++) {//cout << " siz " << i << " " << ye[i] << endl;if (siz[i] == 0) break;//ans = (ans+(pre*(ye[i]*(qw(siz[i],Mod-2),Mod-2)%Mod)%Mod) * (i)%Mod) % Mod;ans = (ans + pre * ye[i] % P * qw(siz[i], P - 2) % P * (i) % P) % P;pre = pre * ((siz[i] - ye[i]) * (qw(siz[i], Mod - 2)) % Mod)%Mod;//pre = pre * (((siz[i] - ye[i]) % P + P) % P) % P * qw(siz[i], P - 2) % P;}cout << ans; return;
}signed main() {cin >> n;for (int i = 1; i < n; i++) {int u, v; cin >> u >> v;add(u, v), add(v, u);//a[u].push_back(v); a[v].push_back(u);}if (n == 1) {cout << 0; return 0;}dfs(1, 0, 0);solve();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/405211.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【区块链+商贸零售】预付宝:商家数字经济服务平台 | FISCO BCOS应用案例

预付宝商家数字经济服务平台是人民链在金融领域落地的 一个区块链应用&#xff0c;致力于营造诚信消费环境&#xff0c;专治诸如健 身房老板卷款跑路、充值后餐馆倒闭钱拿不回来等令消费 者头疼不已的行业乱象&#xff0c;让消费者可以放心地预付费。 平台应用FISCO BCOS区块链…

设计模式学习[3]---单一职责原则+开放封闭原则

文章目录 前言1. 单一职责1.1 原理阐述1.2 处理方式 2. 开放-封闭原则2.1 原理阐释2.2 举例说明 总结 前言 小项目写多了&#xff0c;比如一些什么管理系统之类的&#xff0c;在接触大型项目的时候往往会将之前的一些面向过程的写法代入。 比如UI以及逻辑处理都放在一个类里面…

Flutter【01】状态管理

声明式编程 Flutter 应用是 声明式 的&#xff0c;这也就意味着 Flutter 构建的用户界面就是应用的当前状态。 当你的 Flutter 应用的状态发生改变时&#xff08;例如&#xff0c;用户在设置界面中点击了一个开关选项&#xff09;你改变了状态&#xff0c;这将会触发用户界面…

25届科大讯飞飞星计划 AI研究算法工程师 面经

目录 一面/技术面 2024/08/15 &#x1f4cb; 总结&#xff1a; 本来应该是在7月底面试的&#xff0c;但因为有事就拖到了现在&#xff0c;或许是飞星计划里最晚面试的一批&#xff1f;面试官很和蔼&#xff0c;问的问题不算难&#xff0c;总体体验还算不错。 一面/技术面 2024/…

洛谷B3981题解

题目描述 &#xff08;你不需要看懂这张图片&#xff1b;但如果你看懂了&#xff0c;会觉得它很有趣。&#xff09; JavaScript 是一种功能强大且灵活的编程语言&#xff0c;也是现代 Web 开发的三大支柱之一 (另外两个是 HTML 和 CSS)。灵活的 JavaScript 包含“自动类型转换…

Python 数据分析之Numpy学习(一)

Python 数据分析之Numpy学习&#xff08;一&#xff09; 一、Numpy的引入 1.1 矩阵/向量的按位运算 需求&#xff1a;矩阵的按位相加 [0,1,4] [0,1,8] [0,2,12] 1.1.1 利用python实现矩阵/向量的按位运算 # 1.通过列表实现 list1 [0, 1, 4] list2 [0, 1, 8]# 列表使用…

【Linux网络】select函数

欢迎来到 破晓的历程的 博客 ⛺️不负时光&#xff0c;不负己✈️ 文章目录 select函数介绍select函数参数介绍select函数返回值select的工作流程TCP服务器【多路复用版】 select函数介绍 在Linux网络编程中&#xff0c;select 函数是一种非常有用的IO多路复用技术&#xff0…

基于Java和GeoTools的Shapefile矢量数据缩略图生成实践

目录 前言 一、关于GeoTools的图片生成 1、关于GtRenderer 2、关于 图像生成架构 3、流式计算绘制 二、全球空间预览生成实战 1、pom.xml中关于图像生成依赖 2、样式设置及地图资源绑定 3、图片生成绘制 4、图片生成测试 三、成果验证 1、全球范围生成 2、我国的范…

redis随笔记

缓存穿透。key不存在。恶意攻击、代码问题。加布隆过滤器&#xff0c;或者为空就返回。 缓存失效&#xff08;击穿&#xff09;。key刚好过期。缓存时间随机数。 缓存雪崩。缓存层宕机&#xff0c;一下子袭击数据库。缓存高可用、限流熔断、提前演练。 布隆过滤器就是一个key…

Python版《超级玛丽+源码》-Python制作超级玛丽游戏

小时候最喜欢玩的小游戏就是超级玛丽了&#xff0c;有刺激有又技巧&#xff0c;通关真的很难&#xff0c;救下小公主还被抓走了&#xff0c;唉&#xff0c;心累&#xff0c;最后还是硬着头皮继续闯&#xff0c;终于要通关了&#xff0c;之后再玩还是没有那么容易&#xff0c;哈…

从并发20到并发120之laravel性能优化

调优成果 遇到问题 单台服务并发20&#xff0c;平均响应时间1124ms&#xff0c;通过htop观察&#xff0c;发现cpu占用率达到100%&#xff08;包括sleep的进程&#xff09;&#xff0c;内存几乎没怎么用。 调优后 单机最大吞吐量达到120 响应时长不超过1000ms 硬件信息 …

EfficientFormer 系列算法

1. EfficientFormer V1 模型 论文地址&#xff1a;https://proceedings.neurips.cc/paper_files/paper/2022/file/5452ad8ee6ea6e7dc41db1cbd31ba0b8-Paper-Conference.pdf EfficientFormer V1 基于 ViT 的模型中使用的网络架构和具体的算子&#xff0c;找到端侧低效的原因。然…

高性能web服务器nginx

目录 nginx简介 服务端 I/O 流程 Nginx 进程结构 Nginx启动流程 nginx的源码编译下载 nginx命令常见参数 nginx的配置文件详解 全局配置优化 nginx的平滑升级和回滚 nginx目录匹配优先级测试&#xff08;因为只支持访问文件&#xff0c;所有不比对匹配目录优先级&…

五、2 移位操作符赋值操作符

1、移位操作符 2、赋值操作符 “ ”赋值&#xff0c;“ ”判断是否相等 1&#xff09;连续赋值 2&#xff09;复合赋值符

C ++初阶:类和对象(上)

目录 &#x1f31e;0.前言 1. 面向过程和面向对象初步认识 2..类的引入与定义 2.1类的引入 2.2类的定义 3.类的访问限定符及其封装 3.1访问限定符 3.2封装 4.类的作用域 4.1加餐和发现 5.类的实例化 6.类对象大小的计算 6.1.内部的存储方式 6.2结构体对齐规则回顾…

一、什么是 mvvm? MVC、MVP、MVVM三种模式的区别与详解

简介 MVC、MVP、MVVM都是常见的软件架构模式。 MVC&#xff08;Model-View-Controller&#xff09;架构模式中&#xff0c;将应用程序分为三个主要部分&#xff1a;模型&#xff08;Model&#xff09;、视图&#xff08;View&#xff09;和控制器&#xff08;Controller&…

STM32自制手持小风扇实验

1.1 介绍&#xff1a; 实验功能说明&#xff1a;功能&#xff08;1&#xff09;按一下按键小风扇开启&#xff0c;再按一下关闭。 功能&#xff08;2&#xff09;按一下按键小风扇一档风速&#xff0c;再按一下二挡&#xff0c;依次三挡…关闭。 按键模块说明&#xff1a;按下…

什么是AR、VR、MR、XR?

时代背景 近年来随着计算机图形学、显示技术等的发展&#xff0c;视觉虚拟化技术得到了广泛的发展&#xff0c;并且越来越普及化&#xff0c;慢慢的也走入人们的视野。目前市场上视觉虚拟化技术的主流分为这几种 VR、AR、MR、XR。这几项技术并不是最近才出现的&#xff0c;VR的…

路由器VLAN配置(H3C)

路由器VLAN配置&#xff08;H3C&#xff09; 控制页面访问 路由器默认处于192.168.1.1网段&#xff08;可以短按reset重置&#xff09;&#xff0c;如果要直接使用需要设置静态IP处于同一网段&#xff1b; 对路由器进行配置也要将电脑IP手动设置为同一网段&#xff1b; 默…