从赌徒破产问题到算法竞赛：概率模型与组合计数的实战解析

1. 项目概述从一道竞赛题看概率与组合的深度结合最近在复盘一些经典的算法竞赛题目时2022年牛客多校第十场的H题“Wheel of Fortune”给我留下了深刻的印象。这道题初看像是一个模拟题但深入分析后你会发现它的核心完全建立在概率论与组合数学的精妙结合之上。很多选手在初次接触时可能会试图通过动态规划或者直接模拟游戏过程来求解但这样往往会陷入状态空间爆炸或者计算复杂度极高的困境。这道题的精髓在于它要求你跳出具体的游戏进程从一个更宏观、更数学的视角来审视整个问题将复杂的随机过程转化为可计算的概率模型。简单来说题目描述了一个类似“命运之轮”的对抗游戏。两名玩家各自拥有一个初始生命值HP和一个攻击力ATK。游戏进行多轮每轮开始时系统会等概率地选择一名玩家作为本轮的“目标”。被选中的玩家会受到等同于对方攻击力的伤害即生命值减少。游戏持续进行直到有一名玩家的生命值降至零或以下则该玩家失败另一名玩家获胜。题目给定双方初始的生命值和攻击力需要求解先手玩家通常称为玩家A获胜的概率。这听起来像是一个典型的马尔可夫链问题状态是双方的生命值组合。但直接建模的难点在于生命值可能很大导致状态数量巨大。而“Wheel of Fortune”的巧妙之处在于它通过对称性和组合分析将问题化简为了一个与具体生命值序列无关的、只与攻击次数相关的概率计算问题。理解这个转化过程不仅对解决这道题至关重要更是提升我们面对复杂概率问题时建模能力的一次绝佳训练。无论你是正在备赛的选手还是对概率论感兴趣的程序员相信拆解这道题目的思维过程都会让你有所收获。2. 核心思路解析为什么不能直接模拟当我们拿到一个游戏概率题最直观的想法可能就是模拟。我们定义状态(hp_a, hp_b)表示玩家A和玩家B的当前生命值。然后每个状态都有0.5的概率转移到(hp_a - atk_b, hp_b)B攻击A以及0.5的概率转移到(hp_a, hp_b - atk_a)A攻击B。我们从初始状态开始进行概率DP动态规划直到所有状态都进入“A胜利”或“B胜利”的终止状态。这个思路在理论上是完全正确的但为什么在这道题里行不通呢核心障碍在于数据范围。在竞赛中生命值HP的上限通常很高比如可以达到10^9甚至更大。攻击力ATK虽然相对较小但生命值与攻击力的比值依然巨大。这意味着将玩家生命值降至零所需的攻击次数n和mn ceil(hp_b / atk_a),m ceil(hp_a / atk_b)可能会非常大。状态数量粗略估计是O(n * m)这显然是不可接受的。因此我们必须寻找更优的数学模型。这道题给出的关键提示是游戏的结果只取决于一系列攻击事件发生的顺序而与这些事件发生的具体“时间点”即在哪一轮发生无关。更准确地说我们只关心“使玩家B死亡所需的、由A发出的有效攻击次数”与“使玩家A死亡所需的、由B发出的有效攻击次数”这两类事件在时间轴上的排列顺序。注意这里说的“有效攻击”是指最终对胜负产生决定性的那次攻击。实际上在B生命值归零前A可能对其进行了多次攻击同样在A生命值归零前B也进行了多次攻击。我们最终要比较的是在时间序列上是“A的第n次有效攻击”先发生还是“B的第m次有效攻击”先发生。于是问题被转化了我们有一个无限长的、由独立同分布的伯努利试验构成的序列。每次试验的结果是等概率的“A攻击B”或“B攻击A”。我们不断地进行试验并分别计数。我们关心的事件是在序列中先累计出现n次“A攻击B”的事件还是先累计出现m次“B攻击A”的事件。先出现n次“A攻击B”则A获胜反之则B获胜。这立刻让我们联想到一个经典的概率模型负二项分布Negative Binomial Distribution或与之相关的赌徒破产问题Gambler‘s Ruin的变种。不过这里我们用一个更组合化的视角来理解。3. 概率模型建立组合计数的艺术让我们将游戏过程抽象成一个由字母A和B组成的无限长随机序列。A表示“本轮A攻击B”即对B造成伤害B表示“本轮B攻击A”即对A造成伤害。每次生成A或B的概率都是1/2且相互独立。游戏结束的时刻发生在序列中首次出现“第n个A”或“第m个B”的时候。我们要求A获胜的概率即序列中第n个A出现时B出现的次数尚未达到m次的概率。这个描述引导我们思考一种经典的组合计数方法考虑所有导致A获胜的、有限的序列形态。一个A获胜的序列必然以第n个A结尾并且在这个结尾的A之前B出现的次数k满足0 k m-1。也就是说在游戏结束前B最多只能攻击m-1次。那么对于某个固定的k0 k m-1一个以第n个A结尾且恰好包含k个B的序列是什么样子的呢在最后一个字符即第n个A之前我们必须已经拥有了n-1个A和k个B。这些(n-1) k个事件可以以任意顺序排列。而最后一个位置固定是A。因此对于固定的k满足条件的序列总数为从前面n-1k个位置中选出k个位置放置B剩下的n-1个位置自然放A即组合数C(n-1k, k)。由于每个位置是A还是B的概率都是1/2所以任何一个长度为L的特定序列出现的概率都是(1/2)^L。在我们讨论的情形中序列总长度是(n-1k) 1 n k。所以对于固定的kA以此种方式即B恰好攻击了k次后A完成击杀获胜的概率为P_k C(n-1k, k) * (1/2)^(nk)为什么是(1/2)^(nk)因为序列总共有nk个字符n个A和k个B每个字符的概率是1/2且序列的形态由组合数C(n-1k, k)决定。最后A获胜的总概率就是对所有可能的k从0到m-1求和P_A sum_{k0}^{m-1} [ C(n-1k, k) * (1/2)^(nk) ]这就是本题最核心的概率公式。它优雅地将一个看似需要模拟无限过程的游戏转化为了一个有限的求和问题。其中n ceil(hp_b / atk_a),m ceil(hp_a / atk_b)。3.1 公式的深入理解与边界情况理解这个公式有几点至关重要独立性公式成立的核心前提是每次攻击的目标选择是独立同分布的。这符合题目的等概率描述。“最后一位固定”我们只考虑以A的最后一击结尾的序列。因为游戏在达成终止条件时立即结束所以获胜方的最后一次攻击必定是序列的最后一个事件。这避免了重复计数或漏计。组合数的意义C(n-1k, k)计算的是在最后一击之前攻击事件的所有可能排列数。它体现了“在A完成n次有效攻击的过程中穿插了k次B攻击”的所有可能历史路径。边界值当k0时表示B一次都没攻击A就连续n次攻击并获胜。概率为C(n-1, 0) * (1/2)^n (1/2)^n。当m1时表示B只需要一次有效攻击就能获胜即A的生命值hp_a atk_b。此时求和上限m-10A获胜的概率只有k0这一项即(1/2)^n。这意味着A必须在B第一次出手之前就完成n次攻击否则一旦B出手游戏就结束。这是符合直觉的。实操心得在竞赛中实现这个公式第一个挑战就是计算组合数C(n-1k, k)。由于n和m可能很大k最大为m-1直接计算阶乘会导致溢出。必须使用模运算和乘法逆元在模MOD通常是1e97的意义下进行计算。这意味着我们需要预处理阶乘数组fact[i]和阶乘逆元数组inv_fact[i]以便用C(a, b) fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD来快速查询。4. 算法实现与优化细节理论模型清晰后接下来就是将其转化为高效的代码。我们假设需要在模MOD 1e97下计算答案。4.1 核心计算步骤输入与预处理读取hp_a, atk_a, hp_b, atk_b。计算n (hp_b atk_a - 1) / atk_am (hp_a atk_b - 1) / atk_b。这里使用整数除法上取整的技巧(a b - 1) / b。预处理阶乘与逆元我们需要计算的最大组合数参数是C(n-1 (m-1), m-1)即C(nm-2, m-1)。因此预处理数组的长度至少需要nm为了安全通常设为nm5。预处理fact[0..N]和inv_fact[0..N]。计算概率求和初始化答案ans 0。初始化pow2_inv pow(2, n, MOD)即(1/2)^n在模意义下的值。注意这里是2^n的乘法逆元因为(1/2)^n ≡ pow(2, -n, MOD) ≡ pow(pow(2, n, MOD), MOD-2, MOD)。更高效的做法是计算half (MOD1)//2的幂。循环k从0到m-1计算组合数comb C(n-1k, k)。计算当前项term comb * pow2_inv % MOD。将term加入ans。更新pow2_inv pow2_inv * half % MOD。因为每次k增加1概率分母的2^(nk)就多乘一个1/2。输出结果输出ans % MOD。4.2 代码实现示例PythonMOD 10**9 7 def preprocess_fact(n): 预处理阶乘和阶乘逆元到n fact [1] * (n1) inv_fact [1] * (n1) for i in range(1, n1): fact[i] fact[i-1] * i % MOD inv_fact[n] pow(fact[n], MOD-2, MOD) # 费马小定理求逆元 for i in range(n, 0, -1): inv_fact[i-1] inv_fact[i] * i % MOD return fact, inv_fact def comb(a, b, fact, inv_fact): 计算组合数C(a, b)模MOD if b 0 or b a: return 0 return fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD def solve(): hp_a, atk_a, hp_b, atk_b map(int, input().split()) n (hp_b atk_a - 1) // atk_a # A需要攻击的次数 m (hp_a atk_b - 1) // atk_b # B需要攻击的次数 max_n n m # 需要的最大阶乘参数 fact, inv_fact preprocess_fact(max_n) ans 0 half (MOD 1) // 2 # 1/2 在模MOD下的值 pow_half pow(half, n, MOD) # (1/2)^n for k in range(m): # k从0到m-1 comb_val comb(n - 1 k, k, fact, inv_fact) term comb_val * pow_half % MOD ans (ans term) % MOD pow_half pow_half * half % MOD # 更新为 (1/2)^(nk1) print(ans % MOD) if __name__ __main__: solve()4.3 关键优化与解释逆元的预处理使用费马小定理a^(MOD-2) ≡ a^(-1) (mod MOD)来求逆元。预处理inv_fact时先计算最大的inv_fact[N]然后递推inv_fact[i-1] inv_fact[i] * i % MOD这是线性时间内预处理所有阶乘逆元的标准方法。幂的递推在循环中我们不是每次都用pow(half, nk, MOD)重新计算幂而是利用pow_half变量递推。初始为(1/2)^n每轮循环乘以half即1/2就得到了下一轮需要的(1/2)^(nk1)。这避免了重复的快速幂运算将复杂度从O(m log MOD)降到了O(m)。复杂度分析预处理阶乘是O(nm)主循环是O(m)。因此总时间复杂度为O(nm)在n, m高达10^7数量级时仍然可行在竞赛环境中通常n, m在10^6级别已足够处理本题数据。注意事项务必注意组合数C(n-1k, k)中n-1可能为负数的情况吗不会。因为n是上取整整数至少为1。当n1时n-10组合数C(k, k)1这在数学和代码中都是合理的。我们的comb函数也处理了b0的情况。5. 思维拓展与常见变种分析“Wheel of Fortune”的解法之所以漂亮在于它揭示了处理一类多阶段独立伯努利试验中先达到某计数次数为胜问题的通用思路。我们可以从这个模型出发探讨几种变种和常见的思维陷阱。5.1 变种1攻击概率不相等如果题目修改为每轮A被选中的概率是pB被选中的概率是qpq1那么公式该如何调整思路完全一致只是概率权重变了。在固定k的情况下序列有n个A和k个B。但此时每个特定序列出现的概率不再是(1/2)^(nk)而是p^n * q^k。因为每个A事件发生的概率是p每个B事件发生的概率是q。因此新的公式为P_A sum_{k0}^{m-1} [ C(n-1k, k) * p^n * q^k ]在模运算下我们需要计算p和q的模逆元如果p,q是分数形式给出。实现时可以预处理p_pow_n p^n然后在循环中递推q_pow_k。5.2 变种2游戏平局或提前终止原题是直到一方生命值归零。如果规则改为当一方生命值归零时游戏立即停止或者存在“同归于尽”双方同时归零算平局的情况模型会复杂一些。立即停止我们的模型已经隐含了这个条件因为我们的序列是以获胜方的最后一次攻击结尾的之后的攻击不再发生。同归于尽这需要定义“同时”的含义。如果是在同一轮由于每轮只攻击一次理论上不可能同时。如果是指A的最后一击和B的最后一击发生在不同的轮次但都使得对方生命值归零那么游戏会在先发生的那一击时停止不存在“后一击”。所以原模型仍然适用。如果规则允许“反击”即濒死前还能出手那将变成一个完全不同的状态转移问题。5.3 一个经典的思维陷阱错误的对偶计数一个常见的错误思路是A获胜的概率等于“在至少进行n次A攻击的游戏中A攻击次数先达到n的概率”。然后去计算所有长度为L (L nm-1)的、第n个A出现在第m个B之前的序列。这种计数非常复杂容易重复。我们的方法固定最后一个是A计数前面的排列之所以正确是因为它巧妙地利用了游戏立即停止的特性确保了每个获胜局面被唯一地对应到一种序列形态上以获胜方的致命一击结尾。这是组合计数中“固定结尾法”的典型应用。5.4 与“赌徒破产”问题的联系这个问题也可以看作一个赌徒破产问题的离散时间版本。将A的“资本”初始设为n需要击杀B的次数B的“资本”初始设为m。每轮赌局A以1/2概率赢1单位B的资本减1以1/2概率输1单位A的资本减1。当一方资本归零时破产。A最终获胜即B先破产的概率经典公式为P_A (1 - (q/p)^n) / (1 - (q/p)^(nm))当pq1/2时简化为P_A n / (nm)。等等这和我们推导的求和公式结果一样吗是的当pq1/2时可以证明sum_{k0}^{m-1} C(n-1k, k) * (1/2)^(nk) n / (nm)。这是一个有趣的组合恒等式。但在竞赛中直接使用n/(nm)的公式行不行不行因为我们的n和m是攻击次数而经典赌徒破产模型要求每局输赢是对称的资本增减1。在我们的游戏中每次攻击减少的是对方的“资本”这正好是对称的。所以理论上当pq1/2时答案就是n/(nm)。重要发现这提供了一个更简单的解法为什么我们还要用复杂的组合求和呢原因在于模运算。n/(nm)是一个分数在模MOD下它等于n * inv(nm) % MOD其中inv是模逆元。这个计算量远小于一个可能长达m项的求和。在n, m很大时这简直是降维打击。但是我们必须非常小心经典赌徒破产公式的推导假设了每局赌注是1单位并且资本减少到0为止。在我们的问题中“资本”是“使对方死亡所需的攻击次数”每次攻击确实使对方资本减1。并且pq1/2。条件完全吻合。因此对于原题等概率攻击正确答案就是n / (nm)在模MOD下的值。6. 最终方案与总结反思经过层层分析我们得到了这道题目的两种解法组合求和法P_A sum_{k0}^{m-1} C(n-1k, k) * (1/2)^(nk)优点推导过程直观是解决此类问题的通用方法尤其适用于攻击概率不等的情况。缺点计算复杂度为O(m)当m很大时可能较慢。赌徒破产公式法仅适用于等概率P_A n / (nm)优点计算复杂度为O(log MOD)只需一次快速幂求逆元极其高效。缺点仅适用于双方每轮获胜概率相等的特例。对于2022牛客多校十的H题由于明确是等概率选择所以第二种方法是正解也是出题人预期的考点。很多选手费劲推导组合公式却不知道有这个简洁的结论这反映了知识迁移能力的重要性。6.1 最终代码实现优化版MOD 10**9 7 def solve(): hp_a, atk_a, hp_b, atk_b map(int, input().split()) n (hp_b atk_a - 1) // atk_a m (hp_a atk_b - 1) // atk_b # 使用赌徒破产公式 P n / (nm) numerator n % MOD denominator (n m) % MOD # 计算分母的模逆元 inv_den pow(denominator, MOD-2, MOD) ans numerator * inv_den % MOD print(ans) if __name__ __main__: solve()6.2 从这道题中学到的回顾整个解题过程我们可以提炼出以下几点经验化无限为有限面对无限过程的概率问题优先考虑能否找到决定胜负的有限关键事件这里是攻击次数n和m。抽象与建模将具体的游戏规则抽象为更一般的概率模型独立伯努利试验序列。思考“游戏结果由什么决定”往往比模拟过程更有效。组合计数技巧“固定结尾法”是处理“首次达到”类计数问题的利器。它保证了计数的不重不漏。知识迁移与识别模型识别出问题与经典概率模型如赌徒破产、负二项分布的关联可以极大简化问题。这要求对经典模型的条件和结论非常熟悉。模运算下的计算优化在竞赛编程中不仅要数学上正确还要计算上高效。预处理阶乘逆元、递推幂次、利用模逆元简化分数计算都是必备技能。这道“Wheel of Fortune”就像它的名字一样转动着概率与组合的轮盘。它告诉我们在纷繁复杂的随机过程背后往往隐藏着简洁优美的数学本质。而发现这个本质正是算法竞赛中最迷人的部分。下次当你遇到类似的“多次尝试先到为胜”的问题时不妨先想想它是不是另一个等待被识别的“赌徒破产”呢