当前位置： 首页 > article >正文

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

article 2024/12/24 11:40:17

这里写自定义目录标题

  • 更多精彩内容
    • 256题算法特训课，帮你斩获大厂60W年薪offer
  • 原题
    • 2024ICPC网络赛第二场真题-游戏
    • B站动画详解
  • 问题分析
  • 思路分析
    • 核心思路
    • 递归关系
    • 边界条件
    • 优化思路：辗转相减与辗转相除
    • 最终递归关系
  • 算法实现
  • 代码详解
    • 标准代码程序
      • C++代码
      • Java代码
      • Python代码
      • Javascript代码
  • 复杂度分析
    • 时间复杂度分析
      • 快速幂函数 Power
      • 递归函数 Calc
      • 总体时间复杂度
    • 空间复杂度分析
      • 递归深度
      • 总体空间复杂度
  • 总结

更多精彩内容

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

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

原题

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

B站动画详解

问题分析

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

  1. 初始筹码：

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

  2. 每一轮的结果：

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

  3. 目标：

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

思路分析

核心思路

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

递归关系

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

f ( n , m ) = p 0 ⋅ f ( n , m − n ) + p 1 ⋅ f ( n − m , m ) f(n, m) = p_0 \cdot f(n, m - n) + p_1 \cdot f(n - m, m) f(n,m)=p0​⋅f(n,m−n)+p1​⋅f(n−m,m)

其中：

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

边界条件

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

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

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

具体而言：

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

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

最终递归关系

f ( n , m ) = p 0 k ⋅ f ( n − k ⋅ m , m ) + ( 1 − p 0 k ) f(n, m) = p_0^k \cdot f(n - k \cdot m, m) + \left(1 - p_0^k\right) f(n,m)=p0k​⋅f(n−k⋅m,m)+(1−p0k​)

其中， k = ⌊ n m ⌋ k = \left\lfloor \frac{n}{m} \right\rfloor k=⌊mn​⌋。

算法实现

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

  1. 概率归一化：

    • 计算 p 0 = a 0 a 0 + a 1 m o d    998244353 p_0 = \frac{a_0}{a_0 + a_1} \mod 998244353 p0​=a0​+a1​a0​​mod998244353。
    • 计算 p 1 = a 1 a 0 + a 1 m o d    998244353 p_1 = \frac{a_1}{a_0 + a_1} \mod 998244353 p1​=a0​+a1​a1​​mod998244353。

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

    • 如果 m = 0 m = 0 m=0，返回 1 1 1。
    • 如果 n = 0 n = 0 n=0，返回 0 0 0。
    • 如果 n < m n < m n<m，交换 n n n 和 m m m，同时交换 p 0 p_0 p0​ 和 p 1 p_1 p1​，确保 n ≥ m n \geq m n≥m。
    • 如果 n = m n = m n=m，返回 p 0 p_0 p0​。
    • 计算 k = ⌊ n m ⌋ k = \left\lfloor \frac{n}{m} \right\rfloor k=⌊mn​⌋。
    • 计算 t = p 0 k m o d    998244353 t = p_0^k \mod 998244353 t=p0k​mod998244353。
    • 递归调用 f ( n − k ⋅ m , m ) f(n - k \cdot m, m) f(n−k⋅m,m)。
    • 返回 ( t ⋅ f ( n − k ⋅ m , m ) + ( 1 − t ) ) m o d    998244353 (t \cdot f(n - k \cdot m, m) + (1 - t)) \mod 998244353 (t⋅f(n−k⋅m,m)+(1−t))mod998244353。

  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 ) O(\log k) O(logk)
  • 解释：在计算 a k a^k ak 时，每次循环将指数 k k k 右移一位，相当于除以2，循环次数为 log ⁡ 2 k \log_2 k log2​k。

递归函数 Calc

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

总体时间复杂度

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

空间复杂度分析

递归深度

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

总体空间复杂度

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

总结

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

关键点总结：

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

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

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


http://www.kler.cn/a/326860.html

相关文章：

  • echarts画风向杆
  • linux----文件访问（c语言）
  • 秒优科技-供应链管理系统 login/doAction SQL注入漏洞复现
  • 【spring-cloud-gateway总结】
  • 2.4 网络概念（分层、TCP）
  • ubuntu22.04编译安装Opencv4.8.0+Opencv-contrib4.8.0教程
  • 【容器云】容器云设计方案
  • Linux编译部署PHP环境
  • 冒泡排序-C语言
  • 程序员如何提升核心竞争力——深度耕耘与软技能的培养》
  • HTML元素居中
  • 一款好用的远程连接工具：MobaXterm
  • Xcdoe快速更新安装的小Tips
  • 工业制造场景中的设备管理深度解析
  • QT-文件创建时间修改器
  • 安全运营 -- GPO审计
  • Chrome Cookie最大有效期
  • Web3的愿景：如何构建去中心化的互联网
  • Llama微调以及Ollama部署
  • 阿里云k8s如何创建可用的api token
  • 腾讯云SDK产品优势
  • 4.2.1 通过DTS传递物理中断号给Linux
  • 全面指南：探索并实施解决Windows系统中“mfc140u.dll丢失”的解决方法
  • NAND Flash虚拟层坏块管理机制
  • python爬虫案例——抓取链家租房信息（8）
  • Solaris11.4配置远程桌面登录