2024icpc(Ⅱ)网络赛补题 G
2024icpc(Ⅱ)网络赛补题 G
题目链接:The 2024 ICPC Asia EC Regionals Online Contest (II)
G、Game

题意:
给定Alice和Bob的每一轮的概率 p 0 , p 1 p_0, p_1 p0,p1
给定Alice和Bob的初始数字 x , y x,y x,y。
对于每一轮:
- 如果Alice获胜,则bob的数字 y y y需要减去 x x x。(如果 y ≤ 0 y\leq0 y≤0,Alice获胜)
- 如果Bob获胜,则Alice的数字 x x x需要减去 y y y。(如果 x ≤ 0 x\leq0 x≤0,Bob获胜)
重复上述游戏,直到出现胜利者。
问,Alice最终能赢得游戏的概率有多大。
思路:
可以直接用减法模拟,用除法加速,类似辗转相除法
当 x > y x>y x>y时, x x x可以输 x / y x/y x/y场,转移到 ( x % y , y ) (x\%y,y) (x%y,y)的状态,其他状态A必胜
当 x ≥ y x\geq y x≥y时, x x x必须赢 y / x y/x y/x场,转移到 ( x , x % y ) (x,x\%y) (x,x%y)的状态,然后在考虑A必胜的情况
代码:
const int mod=998244353;
int x,y,a0,a1,b,invb,ans;
int p0,p1;
int quickpow(int x,int y){int res=1;while(y){ if(y&1) res=(res*x)%mod; x=(x*x)%mod;y>>=1;}return res;
}
int inv(int x){return quickpow(x,mod-2);
}
int add(int x,int y){return ((x%mod)+(y%mod))%mod;
}
int sub(int x,int y){return ((x-y)%mod+mod)%mod;
}
int mul(int x,int y){return (x%mod*y%mod)%mod;
}
int dfs(int x,int y,int p){if(x == 0) return 0;if(y == 0) return p;if(x > y){int k = x / y;int cur = quickpow(p1,k);//到达状态(x%y,y)的概率int res = mul(sub(1,cur),p); //(1-cur)*p => A必胜的概率res = add(res,dfs(x%y,y,mul(p,cur))); //res+到达状态(x%y,y)A胜的概率return res;}else{//x<=y 此时A必须赢下k场到达状态(x,y%x)才可能赢int k = y / x;int cur = quickpow(p0,k); int res = mul(cur,p); //到达状态(x,y%x)的概率return dfs(x,y%x,res);}
}
void solve()
{cin >> x >> y >> a0 >> a1 >> b;b = a0 + a1;int invb = inv(b);p0 = mul(a0,invb);p1 = mul(a1,invb);ans = dfs(x,y,1);cout << ans << endl;
}
相关文章:
2024icpc(Ⅱ)网络赛补题 G
2024icpc(Ⅱ)网络赛补题 G 题目链接:The 2024 ICPC Asia EC Regionals Online Contest (II) G、Game 题意: 给定Alice和Bob的每一轮的概率 p 0 , p 1 p_0, p_1 p0,p1 给定Alice和Bob的初始数字 x , y x,y x,y。 对于每一轮: 如果Al…...
AIGC时代!AI的“iPhone时刻”与投资机遇
AIGC时代!AI的“iPhone时刻”与投资机遇 前言AI的“iPhone时刻”与投资机遇 前言 AIGC,也就是人工智能生成内容,它就像是一股汹涌的浪潮,席卷了整个科技世界。它的出现,让我们看到了人工智能的无限潜力,也…...
Kubernetes调度单位Pod
Kubernetes调度单位Pod 1 Pod简介 不直接操作容器container。 一个 pod 可包含一或多个容器(container),它们共享一个 namespace(用户,网络,存储等),其中进程之间通过 localhost 本地…...
C语言指针篇
要想学好C语言,作为灵魂的指针那是必须要掌握的,而要想搞定指针,就不得不讲一下内存和地址之间的关系 内存和地址 计算机上的CPU(中央处理器)在处理数据的时候,需要的数据是在内存中读取的,处…...
Unity 使用Editor工具查找 Prefab 中的指定脚本
在 Unity 项目中,随着项目规模的扩大和 Prefab 数量的增加,管理和定位 Prefab 中的脚本变得更加复杂。为了提高开发效率,所以需要编写一个自定义的 Unity Editor 工具,帮助查找某个 Prefab 中是否使用了指定的脚本。本文将介绍如何…...
Frida-JSAPI:Interceptor使用
拦截器 Interceptor.attach(target, callbacks[, data]) 参数分析 target :target是一个NativePointer,用于指定想要拦截的函数的地址。callbacks :参数是一个包含一个或多个回调函数的对象。 onEnter(args) 回调函数,接收一个参…...
【深度学习】(3)--损失函数
文章目录 损失函数一、L1Loss损失函数1. 定义2. 优缺点3. 应用 二、NLLLoss损失函数1. 定义与原理2. 优点与注意3. 应用 三、MSELoss损失函数1. 定义与原理2. 优点与注意3. 应用 四、BCELoss损失函数1. 定义与原理2. 优点与注意3. 应用 五、CrossEntropyLoss损失函数1. 定义与原…...
git学习报告
文章目录 git学习报告如何配置vscode终端安装PowerShell安装 Microsoft.Powershell.Preview使用 git的使用关于团队合作 git指令本地命令:云端指令 git学习报告 如何配置vscode 安装powershell调教window终端,使其像Linux一样,通过Linux命令…...
Spring MVC的应用
目录 1、创建项目与maven坐标配置 2、核心配置 3、启动项目测试 4、不同请求参数在controller的配置 4.1 servlet API 4.2 简单类型 4.3 pojo类型 4.4 日期类型 4.5 restful风格4种操作类型 4.5.1 GET:获取资源 4.5.2 POST:新建资源 4.5.3 P…...
JavaEE: 深入探索TCP网络编程的奇妙世界(六)
文章目录 TCP核心机制TCP核心机制九: 面向字节流TCP核心机制十: 异常处理 小小的补充(URG 和 PSH)~TCP小结TCP/UDP 对比用UDP实现可靠传输(经典面试题) 结尾 TCP核心机制 上一篇文章JavaEE: 深入探索TCP网络编程的奇妙世界(五) 书接上文~ TCP核心机制九: 面向字节流 TCP是面…...
探秘 Web Bluetooth API:连接蓝牙设备的新利器
引言 随着物联网技术的快速发展,蓝牙设备在日常生活中扮演着越来越重要的角色。而在 Web 开发领域,Web Bluetooth API 的出现为我们提供了一种全新的方式来连接和控制蓝牙设备。本文将深入探讨 Web Bluetooth API 的使用方法和原理,帮助开发…...
Kubernetes Pod调度基础(kubernetes)
实验环境依旧是k8s快照,拉取本次实验所需的镜像文件; 然后在master节点上传已经编写好的yaml文件; 然后同步会话,导入镜像; pod控制器: 标签选择器--》标签: 标签: 在Kubernetes&…...
Angular由一个bug说起之十:npm Unsupported engine
我们在用npm下载包的时候,有时候会碰到这样的提示 这是npm的警告,说我们使用的nodejs版本与下载的包所要求的nodejs版本不一致。 这是因为有些包它对nodejs的版本有要求,然后就会在package.json文件里的engines字段里声明它所要求的nodejs版本…...
Android 开发高频面试题之——Flutter
Android开发高频面试题之——Java基础篇 flutter高频面试题记录 Flutter1. dart中的作用域与了解吗2. dart中. .. ...分别是什么意思?3. Dart 是不是单线程模型?如何运行的?4. Dart既然是单线程模型支持多线程吗?5. Future是什么6. Stream是什么7. Flutter 如何和原生交互…...
视频单目标跟踪研究
由于对视频单目标跟踪并不是很熟悉,所以首先得对该领域有个大致的了解。 视频目标跟踪是计算机视觉领域重要的基础性研究问题之一,是指在视频序列第一帧指定目标 后,在后续帧持续跟踪目标,即利用边界框(通常用矩形框表…...
若依vue3.0表格的增删改查文件封装
一、因若依生成的文件没进行封装,维护起来比较麻烦。所以自己简单的进行封装了一下 gitee代码(文件)地址:https://gitee.com/liu_yu_ting09/ruo_yi.git 二、封装的方法(下面绿色按钮进行全局封装一个JeecgListMixin.js…...
【已解决】如何使用JAVA 语言实现二分查找-二分搜索折半查找【算法】手把手学会二分查找【数据结构与算法】
文章目录 前言任务描述编程要求 输出样例:未查找到11元素! 二、代码实现总结理解不了考试的时候直接背下来就好了。 前言 [TOC]二分搜索 任务描述 折半查找(二分搜索) 设a[low..high]是当前的查找区间,首先确定该区间的中点位置…...
ERROR 1524 (HY000): Plugin ‘mysql_native_password‘ is not loaded
你遇到的错误是由于 MySQL 版本不再默认支持 mysql_native_password 认证插件导致的。从 MySQL 8.0 开始,默认的认证插件是 caching_sha2_password,而不是 mysql_native_password。 解释: 错误 ERROR 1524 (HY000): Plugin mysql_native_pa…...
.NET 6.0 WebAPI 使用JWT生成Token的验证授权
1.引入相关程序包JwtBearer注意版本: 2.配置文件appsettings.json写相关配置参数(也可不写,写在程序里面,数据库读取也是一样的) , //JWT加密"JWTToken": {"SecretKey": "jsaduwqe6asdjewejdue7dfmsdfu0sdfmwmsd8wfsd6",…...
M9410A VXT PXI 矢量收发信机,300/600/1200MHz带宽
M9410A PXI 矢量收发信机 -300/600/1200MHz带宽- M9410A VXT PXI 矢量收发信机,300/600/1200MHz带宽支持 5G 的 PXI 矢量收发信机(VXT)是一个 2 插槽模块,具有 1.2 GHz 的瞬时带宽 主要特点 Keysight M9410A VXT PXIe 矢量收发…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
