当前位置: 首页 > news >正文

【数学】第十三届蓝桥杯省赛C++ A组/研究生组《爬树的甲壳虫》(C++)

【题目描述】

有一只甲壳虫想要爬上一棵高度为 n 的树,它一开始位于树根,高度为 0,当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根,求它从树根爬到树顶时,经过的时间的期望值是多少。

【输入格式】

输入第一行包含一个整数 n 表示树的高度。

接下来 n 行每行包含两个整数 xi,yi,用一个空格分隔,表示 Pi=xi / yi。

【输出格式】

输出一行包含一个整数表示答案,答案是一个有理数,请输出答案对质数 998244353 取模的结果。

其中有理数 a / b 对质数 P 取模的结果是整数 c 满足 0≤c<P 且 c⋅b≡a(modP)。

【数据范围】

对于 20% 的评测用例,n≤2,1≤xi<yi≤20;
对于 50% 的评测用例,n≤500,1≤xi<yi≤200;
对于所有评测用例,1≤n≤100000,1≤xi<yi≤10的9次方,为了保证不出现无解的情况,额外增加限制条件 yi−xi≠998244353(如不增加此条件,则可能出现无解情况,此为比赛原题考虑不周)。

【输入样例1】

1

2

【输出样例1】

2

【输入样例2】

3
1 2
3 5
7 11

【输出样例2】

623902744

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int P = 998244353;int n;LL qmi(int a, int b)
{LL res = 1;while (b){if (b & 1) res = res * a % P;a = (LL)a * a % P;b >>= 1;}return res;
}int main()
{scanf("%d", &n);int res = 0;while (n -- ){int x, y;scanf("%d%d", &x, &y);res = (res + 1ll) * y % P * qmi(y - x, P - 2) % P;}printf("%d\n", res);return 0;
}

相关文章:

【数学】第十三届蓝桥杯省赛C++ A组/研究生组《爬树的甲壳虫》(C++)

【题目描述】 有一只甲壳虫想要爬上一棵高度为 n 的树&#xff0c;它一开始位于树根&#xff0c;高度为 0&#xff0c;当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根&#xff0c;求它从树根爬到树顶时&#xff0c;经过的时间的期望值是多少。 【输入格式…...

Java毕业设计 基于springboot vue招聘网站 招聘系统

Java毕业设计 基于springboot vue招聘网站 招聘系统 springboot vue招聘网站 招聘系统 功能介绍 用户&#xff1a;登录 个人信息 简历信息 查看招聘信息 企业&#xff1a;登录 企业信息管理 发布招聘信息 职位招聘信息管理 简历信息管理 管理员&#xff1a;注册 登录 管理员…...

Leetcode 1. 两数之和

心路历程&#xff1a; 很简单的题&#xff0c;双层暴力就可以&#xff0c;用双指针的话快一点。暴力时间复杂度O( n 2 n^2 n2)&#xff0c;双指针时间复杂度O(nlogn) O(n) O(n) O(nlogn)。 注意的点&#xff1a; 1、题目需要返回原数组的索引&#xff0c;所以排序后还需要…...

【elasticsearch实战】从零开始设计全站搜索引擎

业务需求 最近需要一个全站搜索的功能&#xff0c;我们的站点的特点是数据多源&#xff0c;即有我们本地数据库&#xff0c;也包含了第三方数据源&#xff0c;我们的数据类型除了网页&#xff0c;还包括了各种类型的文档&#xff0c;例如&#xff1a;doc、pdf、excel、ppt等格…...

基于tcp协议的网络通信(基础echo版.多进程版,多线程版,线程池版),telnet命令

目录 基础版 思路 辅助函数 服务端 代码 运行情况 -- telnet ip 端口号 传输的数据为什么没有转换格式 客户端 思路 代码 多进程版 引入 问题 解决 注意点 服务端 代码 运行情况 进程池版(简单介绍) 多线程版 引入 问题解决 注意点 服务端 代码 …...

Ubuntu20系统安装完后没有WIFI

Ubuntu20系统安装完后没有WIFI 查看后发现是缺少网卡&#xff0c;经过查询之后&#xff0c;发现是HRex39/rtl8852be 然后查询了Kernel版本 Check the Kernel Version in Linux $ uname -srm Linux 5.15.0-67-generic x86_64然后进行下载安装 Build(for kernel < 5.18) …...

计算机视觉——目标检测(R-CNN、Fast R-CNN、Faster R-CNN )

前言、相关知识 1.闭集和开集 开集&#xff1a;识别训练集不存在的样本类别。闭集&#xff1a;识别训练集已知的样本类别。 2.多模态信息融合 文本和图像&#xff0c;文本的语义信息映射成词向量&#xff0c;形成词典&#xff0c;嵌入到n维空间。 图片内容信息提取特征&…...

log4j2.xml配置文件不生效

问题 使用springboot配置log4j2&#xff0c;添加了依赖并排除默认的logging依赖&#xff0c;配置了log4j2.xml文件&#xff0c;放在scr目录下&#xff0c;运行可以在控制台输出日志&#xff0c;但不受配置文件影响 解决 配置文件log4j2.xml放在resources目录下生效...

QT信号与槽实现方式

1、第一种实现方式 在QT开发工具UI界面先拖入按钮&#xff0c;然后鼠标右键拖入按钮&#xff0c;点击选中槽&#xff0c;在页面选着需要的信号&#xff0c;然后OK&#xff0c;随即将会跳转到类的.cpp文件&#xff0c;&#xff08;这种UI代码结合的方式&#xff0c;会自动去绑定…...

Yarn面试重点

文章目录 1. 简述Yarn集群的架构2. Yarn 的任务提交流程是怎样的&#xff1f;3. yarn的资源调度的三种模型 1. 简述Yarn集群的架构 YARN&#xff08;Yet Another Resource Negotiator&#xff09;是Hadoop 2.x引入的资源管理器&#xff0c;用于管理Hadoop集群中的资源和作业调…...

高速口光口通信

1.通过transceiver ip 设置好硬件连接配置 2.open example 用自己的模块替换掉tx和rx数据模块 3.大小端问题—— 4.配置gt收发器的rx的k码时候需要设置anybyte便于高效率接收。 5.开发数据产生模块和接收校验模块都需要使用TXUSRCLK2,但是TXUSRCLK线速度/内部数据位宽。——…...

python--剑指offer--15. 二进制中1的个数

编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位数为 ‘1’ 的个数&#xff08;也被称为 汉明重量).&#xff09;。 提示&#xff1a; 请注意&#xff0c;在某些语言&#xff08;如 Java&…...

uniapp h5 部署

uniapp 配置 服务器文件路径 打包文件结构 //nginx 配置 server {listen 8300;server_name bfqcwebsiteapp;charset utf-8;#允许跨域请求的域&#xff0c;* 代表所有add_header Access-Control-Allow-Origin *;#允许带上cookie请求add_header Access-Control-Allow-C…...

排序算法:快速排序(递归)

文章目录 一、创始人托尼霍尔的快速排序二、挖坑法三、前后指针法 所属专栏:C初阶 引言&#xff1a;这里所说的快速排序有三种&#xff0c;第一种是霍尔大佬自创的&#xff0c;还有一种叫做挖坑法&#xff0c;另外一种叫前后指针法 一、创始人托尼霍尔的快速排序 1.这里我们先…...

蓝桥杯每日一题(BFS)

1562 微博转发 开始思路错误点&#xff1a;在用拉链法保存关注信息的时候&#xff0c;因为要看一个用户发的有多少转发的&#xff0c;所以要以用户为坑位&#xff0c;所有关注这个坑位的用户为链表。&#xff08;开始弄反了&#xff09; e数组存某个用户的idx&#xff0c;ne是…...

【C语言】linux内核pci_save_state

一、中文注释 //include\linux\pci.h /* 电源管理相关的例程 */ int pci_save_state(struct pci_dev *dev);//drivers\pci\pci.c /*** pci_save_state - 在挂起前保存PCI设备的配置空间* dev: - 我们正在处理的PCI设备*/ int pci_save_state(struct pci_dev *dev) {int i;/* X…...

轻松打造完美原型:9款在线工具推荐

早年&#xff0c;UI设计师选择的工具有限&#xff0c;功能相对单一&#xff0c;大多数在线原型设计工具都是国外的&#xff0c;语言和网络都增加了设计工作的负担。如今&#xff0c;国内外有许多在线原型设计工具&#xff0c;不仅可以在浏览器上使用&#xff0c;而且还具有团队…...

Vue3中Pinia状态管理库学习笔记

pinia的基本使用 <template><div><h2>Home View</h2> <h2>count:{{ counterStore.count }}</h2><h2>count:{{ count }}</h2><button click"increment">count1</button></div> </template>…...

共谋企业出海新篇章纷享销客荣获数字中国企业峰会“卓越成果奖”

3月9日&#xff0c;2024数字中国企业峰会在杭州西湖中维香溢大酒店成功举办&#xff0c;众多数字化领域专家、知名企业 CIO 代表到场。峰会旨在推动数字化转型与创新发展&#xff0c;为企业出海和国际合作搭建交流与合作的平台。本次峰会的颁奖环节&#xff0c;纷享销客凭借其卓…...

【MySQL】group_concat 函数和 locate 函数运用之找到每篇文章的主题

力扣题 1、题目地址 2199. 找到每篇文章的主题 2、模拟表 表&#xff1a;Keywords Column NameTypetopic_idintwordvarchar (topic_id, word) 是该表的主键&#xff08;具有唯一值的列的组合&#xff09;。该表的每一行都包含一个主题的 id 和一个用于表达该主题的词。可…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...