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 矢量收发…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
