【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;          // 初始化结果为1
    a %= MOD;             // 确保 a 在模 MOD 范围内
    while(k > 0){
        if(k & 1){        // 如果当前位为1，累乘到结果中
            res = 1LL * res * a % MOD;
        }
        a = 1LL * a * a % MOD; // a = a^2 mod MOD
        k >>= 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 MOD
    int t = Power(b, n / m);
    // 更新 y = t * u mod MOD
    y = 1LL * t * u % MOD;
    // 更新 x = (1 - t + t * v) mod MOD
    x = (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 MOD
    int p0 = 1LL * c * a0 % MOD;
    // 归一化概率 p1 = a1 / (a0 + a1) mod MOD
    int 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 MOD
            long p0 = c * a0 % MOD;
            // 归一化概率 p1 = a1 / (a0 + a1) mod MOD
            long p1 = c * a1 % MOD;
            // 计算 Alice 赢得游戏的概率
            long[] result = calc(n, m, p0, p1);
            System.out.println(result[0]);
        }
    }
}

Python代码

MOD = 998244353

def power(a, k):
    res = 1
    a %= MOD
    while k > 0:
        if k & 1:
            res = res * a % MOD
        a = a * a % MOD
        k >>= 1
    return res

def 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 % MOD
    x = (MOD + 1 - t + t * v) % MOD
    return (x, y)

def work():
    import sys
    input = sys.stdin.read
    data = input().split()
    T = int(data[0])
    ptr = 1
    for _ 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 += 5
        c = inv(a0 + a1)
        p0 = c * a0 % MOD
        p1 = c * a1 % MOD
        x, 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. 复杂度分析：详细分析了算法的时间和空间复杂度，确保在高测试用例量下的可行性。

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

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