圣遗物 - 题解

标签与难度

标签: 概率论, 组合数学, 模块化算术, 费马小定理, 快速幂, 数学 难度: 1500

题目大意喵~

一位可爱的原批朋友要打 n 个圣遗物，他想知道，在打这 n 个圣遗物的过程中，每一次新获得的圣遗物都恰好是当时已有的所有圣遗物里最好的或者最坏的，这件事发生的概率是多少呢，喵~？

题目告诉我们，任意两个圣遗物的好坏都有严格的区分，不会出现两个一样好的情况。我们需要把最后计算出的概率对 998244353 取模。

举个栗子，如果 n=3：

• 第一次打出圣遗物 A。
• 第二次打出圣遗物 B。B 要么比 A 好，要么比 A 差。（这总是成立的）
• 第三次打出圣遗物 C。C 必须比 A 和 B 都好，或者比 A 和 B 都差。

我们要计算的就是满足这样条件的总概率，喵~

解题思路分析

这道题看起来可能有点复杂，但只要我们一步一步地分析，就会发现其中的规律，就像猫猫追着毛线球一样，总能找到线头的说！ฅ^•ﻌ•^ฅ

我们可以把整个过程看作是连续 n 个步骤，我们来分析每一步成功的概率是多少。

假设我们正在获取第 i 个圣遗物。在此之前，我们已经成功获取了 i-1 个符合条件的圣遗物。让我带你看看会发生什么吧！

• 第 1 步: 获得第 1 个圣遗物。因为没有其他圣遗物可以比较，所以它既是“最好的”也是“最坏的”。所以，这一步成功的概率是 $1$。

• 第 2 步: 获得第 2 个圣遗物。我们已经有 1 个圣遗物了。新来的这第 2 个，因为好坏是严格区分的，所以它要么比第 1 个好，要么比第 1 个差。这两种情况都满足条件！所以，这一步成功的概率也是 $1$。

• 第 3 步: 获得第 3 个圣遗物。现在我们手里已经有 2 个圣遗物了，一个好的，一个坏的。新来的第 3 个圣遗物的品质，相对于前两个，有三种可能的位置：

  1. 比前两个都差（成为新的最坏）。
  2. 品质介于前两个之间。
  3. 比前两个都好（成为新的最好）。

  我们来画个图理解一下，喵~ (最坏的) <--- slot 1 ---> (已有的1) <--- slot 2 ---> (已有的2) <--- slot 3 ---> (最好的)

  新来的圣遗物，它的品质可以随机地落入这 3 个“空位”中的任何一个。题目要求它必须是最好或最坏的，也就是要落入 slot 1 或者 slot 3。

  因为每种情况都是等可能的，所以在 3 种可能性中，有 2 种是我们想要的。所以，在第 3 步成功的概率是 $\frac{2}{3}$。

• 第 i 步 (i > 2): 获得第 i 个圣遗物。此时我们已经有 i-1 个圣遗物了。我们可以把这 i-1 个圣遗物按品质排成一排。这样就形成了 i 个可以插入新圣遗物的“空位”（包括最前面和最后面）。

  (最坏的) <--- slot 1 ---> (圣遗物1) <--- slot 2 ---> ... <--- slot i-1 ---> (圣遗物 i-1) <--- slot i ---> (最好的)

  要满足条件，新来的圣遗物必须是当前所有圣遗物中最好或最坏的，也就是说，它的品质必须落在最左边的 slot 1 或最右边的 slot i。

  在 i 个等可能的空位中，有 2 个是符合条件的。所以，在第 i 步成功的概率是 $\frac{2}{i}$。

好啦，现在我们知道了每一步成功的概率，总的概率就是把它们全部乘起来！

$$P(n) = P(\text{step 1}) \times P(\text{step 2}) \times P(\text{step 3}) \times \cdots \times P(\text{step n})$$

代入我们刚才分析出的概率：

$$P(n) = 1 \times 1 \times \frac{2}{3} \times \frac{2}{4} \times \cdots \times \frac{2}{n}$$

这个式子对于 $n \ge 2$ 成立。我们可以把它整理一下：

$$P(n) = \frac{2 \times 2 \times \cdots \times 2 \text{ (共 n-2 个 2)}}{3 \times 4 \times \cdots \times n} = \frac{2^{n-2}}{3 \times 4 \times \cdots \times n}$$

为了让分母变成阶乘的样子，我们给分子分母同时乘以 $2$：

$$P(n) = \frac{2^{n-2} \times 2}{(2 \times 3 \times 4 \times \cdots \times n)} = \frac{2^{n-1}}{n!}$$

这个漂亮的公式就是我们最终的答案啦！它对于 $n=1$ ($2^0/1! = 1$) 和 $n=2$ ($2^1/2! = 1$) 也成立，真是太完美了，喵~

计算方法

我们的任务是计算 $\frac{2^{n-1}}{n!}$ 在模 998244353 下的值。 因为 998244353 是一个质数，我们可以使用费马小定理来处理除法。 费马小定理告诉我们，如果 $p$ 是一个质数，那么对于任意整数 $a$，$a^{p-1} \equiv 1 \pmod p$。 由此可以推导出 $a$ 的模逆元是 $a^{p-2} \pmod p$，也就是 $\frac{1}{a} \equiv a^{p-2} \pmod p$。

所以，我们的计算式就变成了：

$$(2^{n-1} \times (n!)^{-1}) \pmod p \equiv (2^{n-1} \times (n!)^{p-2}) \pmod p$$

我们可以分三步来计算：

1. 计算 $F = n! \pmod p$。
2. 计算 $A = 2^{n-1} \pmod p$。
3. 计算 $B = F^{p-2} \pmod p$。
4. 最终答案就是 $(A \times B) \pmod p$。

其中，第 2 步和第 3 步的幂运算可以用快速幂来高效完成，喵~

代码实现

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

#include <iostream>

// 使用 long long 来防止中间计算溢出，喵~
using int64 = long long;

// 模数，一个可爱的质数
const int64 MOD = 998244353;

// 快速幂函数，用来计算 (base^exp) % mod
// 就像猫猫跳跃一样，每次跳一半的路程，很快就到啦！
int64 power(int64 base, int64 exp) {
    int64 result = 1;
    base %= MOD;
    while (exp > 0) {
        // 如果指数是奇数，就把当前的 base 乘到结果里
        if (exp % 2 == 1) {
            result = (result * base) % MOD;
        }
        // 底数平方，指数减半
        base = (base * base) % MOD;
        exp /= 2;
    }
    return result;
}

// 模逆元函数，利用费马小定理
// 1/n 在模 MOD 下的等价值
int64 modInverse(int64 n) {
    return power(n, MOD - 2);
}

int main() {
    // 为了让输入输出更快一点，就像猫猫的反应速度一样！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 处理 n=1 和 n=2 的特殊情况，虽然我们的公式也适用，但分开写更清晰~
    if (n <= 2) {
        std::cout << 1 << std::endl;
        return 0;
    }

    // 计算分子: 2^(n-1) mod MOD
    int64 numerator = power(2, n - 1);

    // 计算分母: n! mod MOD
    int64 factorial_n = 1;
    for (int i = 1; i <= n; ++i) {
        factorial_n = (factorial_n * i) % MOD;
    }

    // 计算分母的模逆元: (n!)^(-1) mod MOD
    int64 inv_factorial_n = modInverse(factorial_n);

    // 最终答案 = 分子 * 分母的逆元
    int64 final_probability = (numerator * inv_factorial_n) % MOD;

    std::cout << final_probability << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(N)$ 我们来分析一下时间都花在哪里了，呐。

  1. 计算 $n!$ 需要一个从 $1$ 到 $n$ 的循环，所以是 $O(N)$。
  2. 计算 $2^{n-1}$ 使用快速幂，时间复杂度是 $O(\log N)$。
  3. 计算 $n!$ 的模逆元，也是用快速幂，时间复杂度是 $O(\log(\text{MOD}))$。

  这几部分中，计算阶乘的 $O(N)$ 是最耗时的，所以总的时间复杂度就是 $O(N)$ 啦。

• 空间复杂度: $O(1)$ 我们只用了几个变量来存 n、阶乘结果、分子、最终答案等，没有使用额外的数组或者数据结构。所以空间复杂度是常数级别的，喵~

知识点总结

这道题虽然简单，但涉及到的知识点可是很有用的哦！

1. 概率论基础: 将复杂事件分解为一系列简单独立（或条件）事件，然后将它们的概率相乘。这是解决很多概率问题的基本思路！
2. 组合分析: 通过分析可能的位置（“空位”思想），来确定每一步的概率，是一种很直观的组合技巧。
3. 模块化算术: 在处理可能非常大的数字时，通过取模来控制其大小，是算法竞赛中的必备技能。
4. 费马小定理与模逆元: 解决了在模意义下的除法问题。只要模数是质数，我们就可以用 $a^{p-2}$ 来代替 $1/a$。
5. 快速幂 (Binary Exponentiation): 一个在 $O(\log b)$ 时间内计算 $a^b$ 的高效算法，在计算模逆元和处理带幂的公式时非常有用。

希望这篇题解能帮到你，如果还有问题，随时可以再来问我哦！祝你刷题愉快，每次都能AC，喵~ (ฅ'ω'ฅ)