【888题竞赛篇】第十二题，2024ICPC网络赛第二场-游戏(Game)

更多精彩内容

这里是带你游历编程世界的Dashcoding编程社，我是Dash/北航硕士/ICPC区域赛全国排名30+/给你呈现我们眼中的世界！

256题算法特训课，帮你斩获大厂60W年薪offer

原题

2024ICPC网络赛第二场真题-游戏

B站动画详解

问题分析

Alice 和 Bob 正在进行一场游戏，游戏的规则如下：

1. 初始筹码：

   • Alice 拥有 $n$ 个筹码。
   • Bob 拥有 $m$ 个筹码。

2. 每一轮的结果：

   • Alice 赢：
     • 概率：$p_0=\frac{a_0}{a_0+a_1}$
     • 操作：
       • 如果 Alice 的筹码 $n$ 大于或等于 Bob 的筹码 $m$，Alice 赢得整个游戏。
       • 否则，Bob 失去 Alice 当前的筹码数，即 $m=m-n$。
   • Bob 赢：
     • 概率：$p_1=\frac{a_1}{a_0+a_1}$
     • 操作：
       • 如果 Bob 的筹码 $m$ 大于或等于 Alice 的筹码 $n$，Bob 赢得整个游戏。
       • 否则，Alice 失去 Bob 当前的筹码数，即 $n=n-m$。
   • 平局：
     • 概率：$1-p_0-p_1$（根据题目提示，这部分可以忽略，因为题目中提到平局无效，我们可以将其视为游戏状态不变）。

3. 目标：

   • 计算 Alice 最终赢得整个游戏的概率，结果需对 $998244353$ 取模。

思路分析

核心思路

问题的关键在于模拟 Alice 和 Bob 之间的筹码变动过程，并计算 Alice 最终赢得整个游戏的概率。由于每一轮的结果依赖于当前的筹码状态，我们可以使用递归或动态规划的方法来解决。

递归关系

设 $f(n,m)$ 表示在 Alice 拥有 $n$ 个筹码，Bob 拥有 $m$ 个筹码的状态下，Alice 赢得整个游戏的概率。那么：

$$f(n,m)=p_0\cdot f(n,m-n)+p_1\cdot f(n-m,m)$$

其中：

• 如果 Alice 赢得一轮（概率 $p_0$），则 Bob 失去 $n$ 个筹码，新的状态为 $(n,m-n)$。
• 如果 Bob 赢得一轮（概率 $p_1$），则 Alice 失去 $m$ 个筹码，新的状态为 $(n-m,m)$。

边界条件

• 当 $m=0$ 时：Bob 没有筹码，Alice 赢得整个游戏，$f(n,0)=1$。
• 当 $n=0$ 时：Alice 没有筹码，无法赢得游戏，$f(0,m)=0$。
• 当 $n=m$ 时：无论谁赢，都会立即结束游戏，因此：
  • Alice 赢的概率 $f(n,n)=p_0$。
  • Bob 赢的概率 $1-p_0$。

优化思路：辗转相减与辗转相除

直接使用递归方法可能导致大量重复计算，尤其是在 $n$ 和 $m$ 较大的情况下。为此，我们可以借鉴辗转相除法（Euclidean Algorithm）的思想，通过一次性处理多个减法操作，加速计算过程。

具体而言：

1. 辗转相减：不断用较大的数减去较小的数，直到两数相等，得到最大公约数（GCD）。
2. 辗转相除：通过除法操作一次性减去多个较小数的倍数，减少递归或迭代的深度。

在本问题中，我们可以通过计算 $k=\lfloor \frac{n}{m}\rfloor$，即 Alice 能够连续赢 $k$ 次，使得 Bob 的筹码减少 $k\cdot m$，从而加速递归过程。

最终递归关系

$$f(n,m)=p_0^k\cdot f(n-k\cdot m,m)+\left(1-p_0^k\right)$$

其中，$k=\lfloor \frac{n}{m}\rfloor$。

算法实现

根据上述分析，我们可以设计以下算法步骤：

1. 概率归一化：

   • 计算 $p_0=\frac{a_0}{a_0+a_1}\mathrm{mod}998244353$。
   • 计算 $p_1=\frac{a_1}{a_0+a_1}\mathrm{mod}998244353$。

2. 递归计算概率 $f(n,m)$：

   • 如果 $m=0$，返回 $1$。
   • 如果 $n=0$，返回 $0$。
   • 如果 $n<m$，交换 $n$ 和 $m$，同时交换 $p_0$ 和 $p_1$，确保 $n\ge m$。
   • 如果 $n=m$，返回 $p_0$。
   • 计算 $k=\lfloor \frac{n}{m}\rfloor$。
   • 计算 $t=p_0^k\mathrm{mod}998244353$。
   • 递归调用 $f(n-k\cdot m,m)$。
   • 返回 $(t\cdot f(n-k\cdot m,m)+(1-t))\mathrm{mod}998244353$。

3. 快速幂与模逆元：

   • 使用快速幂算法计算大指数的幂次方。
   • 使用费马小定理计算模逆元。

代码详解

标准代码程序

C++代码

#include <bits/stdc++.h>// 定义长整型
typedef long long int64;// 定义模数
const int MOD = 998244353;/*** @brief 快速幂函数，计算 a 的 k 次方模 MOD* * @param a 基数* @param k 指数* @return int a^k mod MOD*/
int Power(int a, int k){int res = 1;          // 初始化结果为1a %= MOD;             // 确保 a 在模 MOD 范围内while(k > 0){if(k & 1){        // 如果当前位为1，累乘到结果中res = 1LL * res * a % MOD;}a = 1LL * a * a % MOD; // a = a^2 mod MODk >>= 1;          // 指数右移一位，相当于除以2}return res;
}/*** @brief 计算 a 的模逆元，即 a^(MOD-2) mod MOD* * @param a 被求逆元的数* @return int a 的模逆元*/
int Inv(int a){return Power(a, MOD - 2);
}/*** @brief 递归计算 Alice 赢得游戏的概率* * @param n 当前 Alice 的筹码数* @param m 当前 Bob 的筹码数* @param a Alice 赢得一轮的概率（已归一化）* @param b Bob 赢得一轮的概率（已归一化）* @param x 引用变量，存储 Alice 最终赢得游戏的概率* @param y 引用变量，存储辅助计算值*/
void Calc(int n, int m, int a, int b, int &x, int &y){if(m == 0){           // 基本情况：如果 Bob 没有筹码，Alice 赢得游戏x = 1;y = 0;return;}int u, v;// 递归调用，计算状态 (m, n % m) 下的概率Calc(m, n % m, b, a, u, v);// 计算 t = b^(n / m) mod MODint t = Power(b, n / m);// 更新 y = t * u mod MODy = 1LL * t * u % MOD;// 更新 x = (1 - t + t * v) mod MODx = (MOD + 1 - t + 1LL * t * v) % MOD;
}/*** @brief 处理单个测试用例*/
void work(){int n, m, a0, a1, b_input;std::cin >> n >> m >> a0 >> a1 >> b_input; // 读取输入：n, m, a0, a1, b// 计算概率的逆元 c = Inv(a0 + a1)int c = Inv(a0 + a1);// 归一化概率 p0 = a0 / (a0 + a1) mod MODint p0 = 1LL * c * a0 % MOD;// 归一化概率 p1 = a1 / (a0 + a1) mod MODint p1 = 1LL * c * a1 % MOD;int x, y;// 计算 Alice 赢得游戏的概率Calc(n, m, p0, p1, x, y);// 输出结果std::cout << x << '\n';
}int main(){// 优化输入输出std::ios::sync_with_stdio(false);std::cin.tie(0);int T;std::cin >> T; // 读取测试用例数量while(T--){    // 依次处理每个测试用例work();}return 0;
}

Java代码

import java.io.*;
import java.util.*;public class Main {static final int MOD = 998244353;/*** 快速幂函数，计算 a 的 k 次方模 MOD*/static long power(long a, long k) {long res = 1;a %= MOD;while (k > 0) {if ((k & 1) == 1) {res = res * a % MOD;}a = a * a % MOD;k >>= 1;}return res;}/*** 计算 a 的模逆元，即 a^(MOD-2) mod MOD*/static long inv(long a) {return power(a, MOD - 2);}/*** 递归计算 Alice 赢得游戏的概率*/static long[] calc(int n, int m, long a, long b) {if (m == 0) {return new long[]{1, 0};}long[] uv = calc(m, n % m, b, a);long t = power(b, n / m);long y = t * uv[0] % MOD;long x = (MOD + 1 - t + t * uv[1]) % MOD;return new long[]{x, y};}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// 读取测试用例数量int T = Integer.parseInt(br.readLine());while (T-- > 0) {// 读取每个测试用例String[] parts1 = br.readLine().split(" ");int n = Integer.parseInt(parts1[0]);int m = Integer.parseInt(parts1[1]);String[] parts2 = br.readLine().split(" ");int a0 = Integer.parseInt(parts2[0]);int a1 = Integer.parseInt(parts2[1]);int b_input = Integer.parseInt(parts2[2]);// 计算概率的逆元 c = Inv(a0 + a1)long c = inv(a0 + a1);// 归一化概率 p0 = a0 / (a0 + a1) mod MODlong p0 = c * a0 % MOD;// 归一化概率 p1 = a1 / (a0 + a1) mod MODlong p1 = c * a1 % MOD;// 计算 Alice 赢得游戏的概率long[] result = calc(n, m, p0, p1);System.out.println(result[0]);}}
}

Python代码

MOD = 998244353def power(a, k):res = 1a %= MODwhile k > 0:if k & 1:res = res * a % MODa = a * a % MODk >>= 1return resdef inv(a):return power(a, MOD - 2)def calc(n, m, a, b):if m == 0:return (1, 0)u, v = calc(m, n % m, b, a)t = power(b, n // m)y = t * u % MODx = (MOD + 1 - t + t * v) % MODreturn (x, y)def work():import sysinput = sys.stdin.readdata = input().split()T = int(data[0])ptr = 1for _ in range(T):n = int(data[ptr])m = int(data[ptr + 1])a0 = int(data[ptr + 2])a1 = int(data[ptr + 3])b_input = int(data[ptr + 4])ptr += 5c = inv(a0 + a1)p0 = c * a0 % MODp1 = c * a1 % MODx, y = calc(n, m, p0, p1)print(x)if __name__ == "__main__":work()

Javascript代码

const MOD = 998244353;// 快速幂函数，计算 a 的 k 次方模 MOD
function power(a, k) {let res = 1;a = a % MOD;while (k > 0) {if (k & 1) {res = (res * a) % MOD;}a = (a * a) % MOD;k = Math.floor(k / 2);}return res;
}// 计算 a 的模逆元，即 a^(MOD-2) mod MOD
function inv(a) {return power(a, MOD - 2);
}// 递归计算 Alice 赢得游戏的概率
function calc(n, m, a, b) {if (m === 0) {return [1, 0];}const [u, v] = calc(m, n % m, b, a);const t = power(b, Math.floor(n / m));const y = (t * u) % MOD;const x = (MOD + 1 - t + (t * v) % MOD) % MOD;return [x, y];
}// 处理单个测试用例
function work(input) {const data = input.trim().split(/\s+/).map(Number);let ptr = 0;const T = data[ptr++];const results = [];for (let i = 0; i < T; i++) {const n = data[ptr++];const m = data[ptr++];const a0 = data[ptr++];const a1 = data[ptr++];const b_input = data[ptr++];const c = inv(a0 + a1);const p0 = (c * a0) % MOD;const p1 = (c * a1) % MOD;const [x, y] = calc(n, m, p0, p1);results.push(x);}console.log(results.join('\n'));
}// 读取标准输入
process.stdin.resume();
process.stdin.setEncoding('utf8');
let inputData = '';
process.stdin.on('data', function(chunk) {inputData += chunk;
});
process.stdin.on('end', function(){work(inputData);
});

复杂度分析

时间复杂度分析

快速幂函数 Power

• 时间复杂度：$O(\log k)$
• 解释：在计算 $a^k$ 时，每次循环将指数 $k$ 右移一位，相当于除以2，循环次数为 ${\log }_{2}k$。

递归函数 Calc

• 时间复杂度：$O(\log (n+m))$
• 解释：
  • 类似于辗转相除法，每次递归调用将问题规模缩小为较小的数。
  • 由于每次递归涉及快速幂计算，整体时间复杂度为 $O(\log (n+m))$。

总体时间复杂度

• 单个测试用例：$O(\log (n+m))$
• 所有测试用例：如果有 $T$ 个测试用例，总时间复杂度为 $O(T\cdot \log (n+m))$。

空间复杂度分析

递归深度

• 空间复杂度：$O(\log (n+m))$
• 解释：
  • 递归调用的深度类似于辗转相除法的步骤数，即 $O(\log (n+m))$。
  • 每次递归调用需要常数的额外空间来存储参数和局部变量。

总体空间复杂度

• 总体空间复杂度：$O(T\cdot \log (n+m))$
  • 如果 $T$ 较大且递归深度较深，可能需要考虑优化递归以避免栈溢出。

总结

本文详细分析了一个基于概率和递归关系的游戏问题，探讨了如何利用辗转相减与辗转相除的思想高效计算 Alice 赢得整个游戏的概率。通过递归函数结合快速幂算法，实现了在高效时间复杂度下处理多个测试用例的需求。

关键点总结：

1. 问题建模：将游戏的筹码变动过程建模为递归关系，明确边界条件。
2. 数学原理：借鉴辗转相除法的思想，通过一次性处理多个减法操作，加速递归过程。
3. 算法优化：使用快速幂算法和模逆元计算，确保在大数情况下的高效计算。
4. 多语言实现：提供了 C++、Java、Python、Javascript 四种语言的实现，适应不同编程环境。
5. 复杂度分析：详细分析了算法的时间和空间复杂度，确保在高测试用例量下的可行性。

通过本次分析和实现，读者可以更好地理解如何将数学原理应用于编程问题，特别是在涉及概率和递归关系的复杂问题中。希望本文对您在算法设计和实现上有所帮助。

如果您有任何疑问或需要进一步探讨的内容，欢迎在评论区留言交流！