和的期望 - 题解

标签与难度

标签: 期望, 概率, 数学, 组合数学, 线性期望, 费马小定理, 模运算难度: 1400

题目大意喵~

你好呀，指挥官！这道题是这样的喵~

我们有一个装满数字的数组 a，它有 n 个数字。还有一个一开始空空如也的数组 b。

接下来我们要进行 n 次操作。在每一次操作中，我们都会从数组 a 中等概率地随机选择一个数字，然后把它从 a 中拿出来，放进数组 b 里。这个过程会一直持续，直到数组 a 变空，而数组 b 装满了所有 n 个数字。

我们的任务是，对于每一个操作次数 k（从 1 到 n），计算出操作 k 次之后，数组 b 中所有数字之和的期望值是多少，然后把它们依次输出。所有计算都要在一个很大的质数 998244353 下进行取模哦！

解题思路分析

一看到“期望”两个字，有些同学可能会觉得头皮发麻，感觉很复杂的样子，对吧？别怕别怕，我我来给你分析一下，其实它是一只很温顺的小猫咪哦，喵~

“期望”说白了就是“平均来看，结果会是多少”。我们来一步步拆解这个问题。

我们的目标是求 k 次操作后数组 b 的和的期望，我们把它记作 $E_k$ 。

直接去想所有可能的操作序列和它们对应的和，然后加权平均，那可太复杂啦！比如说，第一次操作有 n 种可能，第二次有 n-1 种...情况太多，会把猫猫的脑子绕晕的！

这时候，我们就要请出概率论中的一个超级好用的魔法——期望的线性性质！

期望的线性性质：简单来说，就是“和的期望”等于“期望的和”。不管这些事件之间是否相互独立，这个性质都成立！公式写出来就是 $E(X+Y) = E(X) + E(Y)$ 。

利用这个性质，我们可以不去看 b 数组整体的和，而是去看原数组 a 中的每一个元素 $a_i$ 对最终期望的贡献。

设原数组是 $A = \{a_1, a_2, \dots, a_n\}$ 。k 次操作后 b 数组的和可以写成：

\text{Sum}_b^{(k)} = \sum_{i=1}^{n} a_i \cdot X_i^{(k)}

这里的 $X_i^{(k)}$ 是一个指示器变量，如果第 $i$ 个元素 $a_i$ 在 k 次操作后被移到了 b 数组里，那么 $X_i^{(k)}=1$ ，否则 $X_i^{(k)}=0$ 。

根据期望的线性性质，我们想求的 $E_k = E[\text{Sum}_b^{(k)}]$ 就等于：

E_k = E\left[\sum_{i=1}^{n} a_i \cdot X_i^{(k)}\right] = \sum_{i=1}^{n} E[a_i \cdot X_i^{(k)}] = \sum_{i=1}^{n} a_i \cdot E[X_i^{(k)}]

一个指示器变量的期望，就等于它所指示的事件发生的概率。所以 $E[X_i^{(k)}]$ 就是 “元素 $a_i$ 在 k 次操作后被移入 b 数组” 这件事的概率。

那么，这个概率是多少呢？

我们来想一下，k 次操作后，b 数组里会有 k 个元素。这些元素是从最初的 n 个元素里选出来的。因为每次都是等概率随机选择，所以最终 b 里的这 k 个元素，就相当于从 n 个元素中随机抽样了 k 个。对于任何一个特定的元素 $a_i$ 来说，它被选中的概率是多少呢？

这就像一个袋子里有 n 个不同的小球，我们随机摸出 k 个，问某个特定的小球被摸出来的概率。很直观地，这个概率就是 $\frac{k}{n}$ ，对吧？

我们也可以稍微证明一下：总共有 $\binom{n}{k}$ 种选择 k 个元素的方法，每种都是等可能的。而包含我们特定元素 $a_i$ 的选法有多少种呢？我们必须选择 $a_i$ ，然后从剩下的 $n-1$ 个元素中再选择 $k-1$ 个，共有 $\binom{n-1}{k-1}$ 种方法。所以概率就是：

P(a_i \text{ 在 } b \text{ 中}) = \frac{\binom{n-1}{k-1}}{\binom{n}{k}} = \frac{\frac{(n-1)!}{(k-1)!(n-k)!}}{\frac{n!}{k!(n-k)!}} = \frac{(n-1)! \cdot k!}{n! \cdot (k-1)!} = \frac{k}{n}

看吧，果然是 $\frac{k}{n}$ ！

最神奇的是，这个概率对于每一个 $a_i$ 都是一样的！

现在我们可以回到我们的期望公式了：

E_k = \sum_{i=1}^{n} a_i \cdot P(a_i \text{ 在 } b \text{ 中}) = \sum_{i=1}^{n} a_i \cdot \frac{k}{n}

我们可以把公共部分 $\frac{k}{n}$ 提取出来：

E_k = \frac{k}{n} \cdot \sum_{i=1}^{n} a_i

令 $S = \sum_{i=1}^{n} a_i$ 为原数组 a 的总和。那么最终的公式就变得超级简单了，喵~

E_k = S \cdot \frac{k}{n}

所以，我们只需要：

计算出原数组 a 的总和 $S$ 。
对于每个 $k$ 从 1 到 $n$ ，计算 $S \cdot k \cdot n^{-1}$ 的值。

因为题目要求在模 998244353 下计算，除以 n 就变成了乘以 n 的模逆元。由于 998244353 是一个质数，我们可以用费马小定理来求逆元，即 $n^{-1} \equiv n^{\text{MOD}-2} \pmod{\text{MOD}}$ 。

这样，问题就迎刃而解啦！是不是很简单呢？

代码实现

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

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 定义一个很长的名字来表示 long long，喵~
using int64 = long long;

// 模数
const int MOD = 998244353;

/**
 * @brief 快速幂函数，用于计算 (base^exp) % mod
 * @param base 底数
 * @param exp 指数
 * @return (base^exp) % mod 的结果
 */
int64 power(int64 base, int64 exp) {
    int64 res = 1;
    base %= MOD;
    while (exp > 0) {
        // 如果指数是奇数，就把当前的 base 乘到结果上
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        // 底数平方
        base = (base * base) % MOD;
        // 指数除以2
        exp /= 2;
    }
    return res;
}

/**
 * @brief 计算模逆元
 * @param n 要求逆元的数
 * @return n 在模 MOD 下的逆元
 * @note 这里使用费马小定理 n^(MOD-2) % MOD
 */
int64 modInverse(int64 n) {
    return power(n, MOD - 2);
}

int main() {
    // 加速 C++ 的 IO，让程序跑得更快，像猫一样敏捷！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int64> a(n);
    int64 total_sum = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        // 累加总和，并且每次都取模，防止溢出
        total_sum = (total_sum + a[i]) % MOD;
    }

    // 计算 n 的模逆元
    int64 inv_n = modInverse(n);

    // 循环计算并输出每个 k 对应的期望值
    for (int k = 1; k <= n; ++k) {
        // E_k = total_sum * k / n
        // 在模运算下，变成 (total_sum * k) * inv_n
        int64 expectation = (total_sum * k) % MOD;
        expectation = (expectation * inv_n) % MOD;
        
        // 输出结果，注意格式，最后一个数字后面没有空格
        std::cout << expectation << (k == n ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$
- 我们首先需要遍历一次数组 a 来计算总和 $S$ ，这需要 $O(N)$ 的时间。
- 接着，我们用快速幂计算 n 的模逆元，时间复杂度是 $O(\log(\text{MOD}))$ ，这是一个常数时间的操作。
- 最后，我们循环 k 从 1 到 n，每次进行几次常数时间的乘法和取模运算，这部分总共需要 $O(N)$ 的时间。
- 所以总的时间复杂度是 $O(N + \log(\text{MOD}))$ , 也就是 $O(N)$ 啦，非常高效！
空间复杂度: $O(N)$
- 我们需要一个大小为 $N$ 的 vector 来存储输入的数组 a。如果题目允许边读边加，甚至可以优化到 $O(1)$ ，但 $O(N)$ 已经完全足够了。

知识点总结

这道题虽然看起来是概率期望题，但核心思想非常巧妙，让我们来总结一下学到了什么吧，喵~

期望的线性性质: 这是解决本题的钥匙！它允许我们将一个复杂问题的整体期望，分解为各个独立部分期望的简单加和。记住这个性质： $E(\sum X_i) = \sum E(X_i)$ ，它非常强大！
贡献法思想: 线性期望常常和“贡献法”一起使用。我们不直接求总和，而是计算每个元素对总和的期望贡献，最后再加起来。
组合概率: 理解在 n 个物品中随机抽取 k 个时，每个物品被选中的概率都是 $\frac{k}{n}$ 。这是一个很基础但非常有用的结论。
模运算与模逆元: 在算法竞赛中，当结果很大时，通常会要求对一个大质数取模。这就要求我们熟练掌握模意义下的加、减、乘法。对于除法，则需要通过求模逆元来转换成乘法。
费马小定理: 当模数 $p$ 是质数时，计算一个数 $a$ 的模逆元最方便的方法就是用费马小定理，即 $a^{p-2} \pmod p$ 。配合快速幂算法，可以高效地完成计算。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！一起加油，喵~！

和的期望 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​