coin - 题解

标签与难度

标签: 概率论, 数论, 组合数学, 快速幂, 费马小定理, 随机游走, 数学难度: 2200

题目大意喵~

一位名叫 Rikka 的小可爱和她的朋友 Yuuta 在玩一个抛硬币的游戏，喵~ 规则是这样的：

他们不断地抛一枚硬币。硬币正面朝上（Rikka 获胜一局）的概率是 $p$ ，反面朝上（Yuuta 获胜一局）的概率是 $1-p$ 。
游戏会在某个时刻结束。结束的条件是：在任意一个连续的时间段里，某个人比另一个人多赢了 $n$ 局。
比如说，当 $n=3$ 时，如果游戏进行了7局，结果是“反反正正反正正”。那么在第2局到第7局这个时间段里（“反正正反正正”），Rikka 赢了4局，Yuuta 赢了2局，Rikka 比 Yuuta 多赢了 $4-2=2$ 局。但如果在第3局到第7局（“正正反正正”），Rikka赢了4局，Yuuta赢了1局，Rikka 多赢了3局，满足了 $n=3$ 的条件，所以 Rikka 赢得整场游戏，游戏结束！

我们的任务就是，计算出 Rikka 最终赢得整场游戏的概率是多少，结果需要对 $998244353$ 取模，呐。

解题思路分析

喵~ 这道题第一眼看上去，可能会觉得是动态规划或者递推。但仔细想想，游戏结束的条件是“任意一个时间段”，这使得状态的定义变得非常困难，因为它需要记录下整个历史信息，这可怎么办呀？

别担心，让我来帮你理清思路！我们可以把这个问题转化成一个更经典的数学模型：一维随机游走 (1D Random Walk)，的说！

想象一条无限长的数轴，我们从原点 $0$ 出发。

每当 Rikka 赢一局（硬币正面），我们就向右走一步（位置 +1）。
每当 Yuuta 赢一局（硬币反面），我们就向左走一步（位置 -1）。

设 $S_k$ 是我们走了 $k$ 步之后的位置，它代表了“Rikka 获胜的局数 - Yuuta 获胜的局数”。那么，“在第 $i$ 局到第 $j$ 局这个时间段内，Rikka 比 Yuuta 多赢了 $k$ 局”，就等价于 $S_j - S_{i-1} = k$ 。

所以，游戏的结束条件就变成了：存在任意的 $i, j$ ( $0 \le i-1 < j$ )，使得 $|S_j - S_{i-1}| = n$ 。这个条件还可以进一步等价于：我们走过的所有点中，最高点和最低点的差值达到了 $n$ 。也就是 $\max(S_k) - \min(S_k) = n$ 。

当这个条件第一次满足时：

如果是由于一个 +1 的步伐（Rikka 赢）导致最高点更新，从而使得极差达到 $n$ ，那么 Rikka 赢得游戏。
反之，如果是由于一个 -1 的步伐（Yuuta 赢）导致最低点更新，从而使得极差达到 $n$ ，那么 Yuuta 赢得游戏。

这道题其实是一个关于随机游走（Random Walk）范围的经典问题，喵~ 它的精确解法通常需要用到生成函数或者鞅（Martingale）这些比较高深的数学工具。直接从头推导会把我的猫毛都绕晕的！不过没关系，我们可以借助前人的智慧，来理解这个神奇的公式是怎么来的，然后我们就能解开这道题的谜题啦，呐~

神奇的公式登场！

设 Rikka 获胜一局的概率为 $p$ ，Yuuta 获胜一局的概率为 $q = 1-p$ 。我们定义一个比率 $x = q/p$ 。 Rikka 最终获胜的概率 $P_R$ 可以用下面这个公式计算：

P_R = \frac{n x^n (x-1)}{(x^{n+1}-1)(x^n-1)} - \frac{1}{x^{n+1}-1}

我们可以把这个公式拆成两部分来计算：

第一项： $T_1 = \frac{n x^n (x-1)}{(x^{n+1}-1)(x^n-1)}$
第二项： $T_2 = \frac{1}{x^{n+1}-1}$

最终答案就是 $(T_1 - T_2) \pmod{998244353}$ 。

特殊情况

当 $p=q=1/2$ 时，我们的比率 $x=q/p=1$ 。这时候，上面的公式分母会变成零，没有意义。这种情况需要特殊处理。当 $p=q$ 时，游戏是完全对称的，Rikka 和 Yuuta 获胜的概率是均等的。所以，Rikka 获胜的概率就是 $1/2$ 。

计算实现

因为题目要求对质数 $998244353$ 取模，所以所有的运算都要在模意义下进行。

除法：要变成乘以它的模逆元。根据费马小定理，一个数 $a$ 在模 $M$ （ $M$ 为质数）下的逆元是 $a^{M-2} \pmod M$ 。
乘方：要用快速幂来高效计算 $a^b \pmod M$ 。

所以，我们的解题步骤就是：

读入 $n$ 和 $p$ （这里的 $p$ 已经是模意义下的值了）。
计算 $q = (1 - p + \text{mod}) \pmod{\text{mod}}$ 。
计算 $x = q \cdot p^{-1} \pmod{\text{mod}}$ ，其中 $p^{-1}$ 是 $p$ 的模逆元。
检查特殊情况：如果 $x=1$ （即 $p=q$ ），答案就是 $1/2$ 的模逆元。
如果 $x \neq 1$ ，就利用快速幂和模逆元，代入上面的公式计算出 $T_1$ 和 $T_2$ 。
最终答案就是 $(T_1 - T_2 + \text{mod}) \pmod{\text{mod}}$ 。

这样，我们就能轻松解决这个问题啦，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，注释超详细的哦！

cpp

#include <iostream>

// 使用 long long 防止中间计算溢出
using ll = long long;

// 我们要在模这个质数下进行计算
const ll MOD = 998244353;

// 快速幂函数，用来计算 (base^exp) % MOD
// 时间复杂度 O(log exp)
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元函数，利用费马小定理计算 a 在模 MOD 下的逆元
// a^{-1} \equiv a^{MOD-2} \pmod{MOD}
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 解决一单测试的核心逻辑
void solve() {
    ll n, p;
    std::cin >> n >> p;

    // Rikka 获胜概率是 p
    // Yuuta 获胜概率是 q = 1 - p
    ll q = (1 - p + MOD) % MOD;

    // 如果 p=0, Rikka 不可能获胜 (除非 n=0, 但题目保证 n>=1)
    if (p == 0) {
        std::cout << 0 << '\n';
        return;
    }
    // 如果 q=0, Yuuta 不可能获胜, Rikka 必胜
    if (q == 0) {
        std::cout << 1 << '\n';
        return;
    }

    // 计算比率 x = q/p
    ll x = (q * modInverse(p)) % MOD;

    // 特殊情况：p = q = 1/2，此时 x = 1
    // 游戏完全对称，Rikka 获胜概率为 1/2
    if (x == 1) {
        std::cout << modInverse(2) << '\n';
        return;
    }

    // 根据公式 P_R = T1 - T2 计算
    // T1 = (n * x^n * (x-1)) / ((x^(n+1)-1) * (x^n-1))
    // T2 = 1 / (x^(n+1)-1)

    ll x_n = power(x, n);
    ll x_n_plus_1 = (x_n * x) % MOD;

    // 计算 T1
    ll t1_numerator = (n * x_n) % MOD;
    t1_numerator = (t1_numerator * (x - 1 + MOD)) % MOD;
    
    ll den_part1 = (x_n_plus_1 - 1 + MOD) % MOD;
    ll den_part2 = (x_n - 1 + MOD) % MOD;
    ll t1_denominator = (den_part1 * den_part2) % MOD;
    
    ll t1 = (t1_numerator * modInverse(t1_denominator)) % MOD;

    // 计算 T2
    ll t2_denominator = den_part1;
    ll t2 = modInverse(t2_denominator);

    // 最终答案
    ll ans = (t1 - t2 + MOD) % MOD;
    std::cout << ans << '\n';
}

int main() {
    // 加速输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot \log n)$ 对于每组测试数据，我们主要的时间开销在于计算快速幂 power(x, n) 和 power(x, n+1)。快速幂的时间复杂度是对数级别的，所以处理一组数据的时间是 $O(\log n)$ 。总共有 $T$ 组数据，所以总时间复杂度是 $O(T \cdot \log n)$ ，非常高效，喵~
空间复杂度: $O(1)$ 我们只使用了几个变量来存储中间结果，没有使用任何随输入规模 $n$ 变化的额外空间，所以空间复杂度是常数级别的。

知识点总结

随机游走模型 (Random Walk): 能够把看似复杂的过程（比如这个硬币游戏）转化为经典的数学模型是解题的关键一步。很多概率题背后都有随机游走的影子哦。
模运算: 在处理计数和概率问题时，当答案需要对一个大质数取模时，所有的加、减、乘、除运算都必须在模意义下进行。
费马小定理与模逆元: 这是处理模意义下除法的标准工具。 $a/b \pmod M$ 等价于 $a \cdot b^{M-2} \pmod M$ 。
快速幂: 高效计算 $a^b \pmod M$ 的不二之选，是数论问题中的基本功。
公式应用: 有时候，解决问题的最快方法是识别出问题所属的领域，并应用该领域内的已知结论（公式）。这需要广泛的知识面和优秀的抽象建模能力，大家一起加油学习吧，喵！

coin - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​