首页 > 其他分享 >【888题竞赛篇】第十二题，2024ICPC网络赛第二场-游戏(Game)

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

时间：2024-09-23 17:53:01浏览次数：11  
标签：log 2024ICPC int 888 Alice a1 a0 Game MOD

这里写自定义目录标题

更多精彩内容

这里是带你游历编程世界的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. 复杂度分析：详细分析了算法的时间和空间复杂度，确保在高测试用例量下的可行性。

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

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

标签：log,2024ICPC,int,888,Alice,a1,a0,Game,MOD
From： https://blog.csdn.net/Dashcoding213/article/details/142463962

相关文章

  • 2024ICPC网络赛2
    赛时5题，G题思路对的不知道为啥没过，对辗转相除法还有递推理解太低是这样的。F，I队友切的签到，I似乎是简单构造A模拟这题离谱的一个地方就是我用unordered_map会报错所以改map了。查了一下语法发现是因为没有自定义哈希函数，所以key值不是常规类型的时候必须自定义哈希函数。（当然......
  • CF2006A Iris and Game on the Tree
    题目链接题解知识点：贪心，博弈论。一个\(01\)串中\(01,10\)的个数差只与首尾两个字符相关，若首尾字符相同，则个数差为\(0\)，否则为\(1\)或\(-1\)。因此，树上除了根节点和叶子节点的\(?\)是不影响叶子节点权值的（但可能影响策略，导致答案不一样），我们只需要考虑叶子节点和根......
  • 2024ICPC网络赛第二场题解(部分)
    前言这场相对作用大一点，最后顶着队友的怀疑压力乱搞出了C，但是后面看题解发现似乎是数据弱了跑过去，其实复杂度是队友分析的那样，是不正确的，但是毕竟是打名额的比赛，过了就是过了，这里分享一下C题的乱搞做法，以及其他题的我们队赛时代码。下面的顺序按过题顺序(也差不多是难度递增顺序)......
  • 2024ICPC网络赛（2）-K.Match——匹配、奇妙的n4 DP
    题目：https://qoj.ac/contest/1799/problem/9380题意：给两个长度为\(n\)的序列\(a,b\)，若\(a_i\oplusb_j\geqk\)则连一条左侧\(i\)到右侧\(j\)的边，这样得到一张二分图。对于每个\(x=1,\dots,n\)，询问大小为\(x\)的匹配的数量。\(1\leqn\leq200\).首先要知道一般二......
  • AI预测福彩3D采取888=3策略+和值012路或胆码测试9月20日新模型预测第93弹
            经过90多期的测试，当然有很多彩友也一直在观察我每天发的预测结果，得到了一个非常有价值的信息，那就是9码定位的命中率非常高，90多期一共只错了10次，这给喜欢打私房菜的朋友提供了极高价值的预测结果~当然了，大部分菜友还是走的正常渠道，因此，得想办法进行缩水，尽可能少......
  • AI预测体彩排3采取888=3策略+和值012路或胆码测试9月20日升级新模型预测第86弹
            经过80多期的测试，当然有很多彩友也一直在观察我每天发的预测结果，得到了一个非常有价值的信息，那就是9码定位的命中率非常高，已到达90%的命中率，这给喜欢打私菜的朋友提供了极高价值的预测结果~当然了，大部分菜友还是走的正常渠道，因此，得想办法进行缩水，尽可能少的缩......
  • 31263 / 32004 Game Development
    31263/32004GameDevelopmentLabWeek6GettingStarted1.Downloadthecorrespondingweek’szipfilefromthisweek’smoduleonCanvas.2.UnziptheprojectfolderandopenitinUnity.Ifthereareanywarningsaboutdifferenceinversions,justconti......
  • 2024ICPC网络赛第一场题解(部分)
    这一场基本纯挂件，给队友翻译翻译题面，帮队友打打板子了，可惜最后40sL题冲了一个\(O(\frac{n^3}{w})\)的bitset最后wa了，所以下面的题解我也只能看着队友代码说说大概，主要参考一下代码吧。A题意给出32个队伍的能力值，和比赛的规则，其中中国队是第一个队伍，问所有分组的情况下，中国队......
  • 游戏创作的梦想之地！EE GAMES 创作者社区上线，VipSkill产学研结合迈开重大步伐
    ＥＥＧＡＭＥＳ官网EEGAMES创作者社区是一个怎样的平台？EEGAMES创作者社区，是专注于链接每一位游戏创作者，提供全方位服务的游戏领域垂类社区。这里不仅仅是一个游戏创作的互助平台，更是每一位游戏创作者的梦想启航之地！无论你是经验丰富的游戏研发行家，还是刚刚起步的业内新人，都可......
  • 通过NandGame网站学习逻辑门
    继电器：电磁继电器由电磁铁和衔铁组成，给电磁铁通电磁铁有磁性会把衔铁吸下来，那么再接上电路，就可以通过电磁铁控制电路开关。如下图所示，左图是电磁铁未接电的状态，左图是电磁铁已接电的状态。继电器是一种可由电流（称为控制电流）控制的开关。控制电流连接到一个磁铁，用于把连接端子......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99