GDKOI2021 提高组第二试：概率计算与游戏策略

"GDKOI2021TGDay2.pdf 是广东省重点中学信息学冬令营提高组第二试的竞赛资料，涉及C++编程语言，包含四道题目：游戏、群岛、抄写和堆。每道题有特定的输入输出文件格式、时间限制和空间限制，并需使用g++4.8.4编译器，64位整数用%lld格式处理。题目评分以源程序为准，最终解释权归GDOI评委会所有。第一题‘游戏’要求计算达到低保所需对局次数的期望值，输入为获胜概率，输出是对期望值取模后的结果。" 在此次竞赛中，参赛者需要使用C++编程解决四道题目。第一题"游戏"是一个概率问题，目标是计算在具有不同获胜概率的情况下，达到特定星数（低保）所需的平均对局次数。题目描述了一个简单的概率模型，玩家在拥有i颗星时，获胜的概率为pi，其中pi可以通过给定的xi和yi来计算，即pi = xi / yi。玩家每次对局要么赢得一颗星，要么失去一颗星（在有星星的情况下），但当星星数为0时，失败不会进一步扣除。 解题的关键在于理解期望值的概念。期望值是概率论中的一个基本概念，表示随机变量的平均值，用于衡量可能结果的平均效果。在这个问题中，我们需要求的是达到低保所需对局次数的期望值。由于每局游戏的结果（赢或输）取决于当前的星星数，因此我们需要计算一系列可能的对局序列及其对应的概率，然后将这些序列的长度乘以其概率并求和。 计算过程中需要注意，题目要求答案对998244353取模。这通常意味着在计算过程中，我们需要使用模运算来避免数值溢出。可以使用动态规划或者迭代的方法来求解，每次更新当前星星数i下的期望值，直到达到低保状态。最后，输出的期望值是对998244353取模后的结果，这个结果可以是任何满足dq ≡ p (mod 998244353) 的整数d。 这道题目考验了参赛者的概率计算能力、动态规划或迭代算法的设计能力，以及在C++中处理大整数和模运算的技巧。其他三题“群岛”、“抄写”和“堆”也应类似，分别围绕不同的主题设置，需要参赛者运用相应的算法和数据结构知识来解决。