概念
数学期望（Mathematical Expectation），也叫均值（Mean）、期望值（Expected Value），是概率论中的一个核心概念。它描述的是在大量重复试验下，随机变量的平均值。
生活中我们经常无意中用到期望的思想。比如你每天上班的路程可能遇到两种情况：
- 不堵车：\(20\) 分钟（概率 \(60%\)）
- 堵车：\(40\) 分钟（概率 \(40%\)）
那么上班时间的期望为：
\(\mathbb{E}[\text{时间}] = 20 \times 0.6 \ +\ 40 \times 0.4 = 12 + 16 = 28 \ \text{分钟}\)
意思是：如果你把每天的通勤时间记录下来，很多很多天取平均，结果会接近 \(28\) 分钟。
数学定义（离散型）
如果一个随机变量 \(X\) 可能取值 \(x_1, x_2, x_3, \dots\)，对应的概率分别为 \(p_1, p_2, p_3, \dots\)（且 \(p_1 + p_2 + \dots = 1\)），那么数学期望定义为：
\(\mathbb{E}[X] = \sum_{i} x_i \cdot p_i\)
就是“可能的结果 × 这个结果的概率，再求和”。
简单例子
例 1：掷硬币
设随机变量 \(X\)：
- 正面 \(= 1\)，反面 \(= 0\)
- \(P(X=1) = 0.5, \quad P(X=0) = 0.5\)
期望： \(\mathbb{E}[X] = 1 \times 0.5 + 0 \times 0.5 = 0.5\)
这意味着：平均每次掷硬币会得到 \(0.5\) 个正面（虽然 \(0.5\) 这个值从来不会真的出现）。
例 2：掷骰子
- \(X\) 取值为 \(1, 2, 3, 4, 5, 6\)
- 每个概率都是 \(1/6\)
期望： \(\mathbb{E}[X] = \frac16 (1+2+3+4+5+6) = \frac{21}{6} = 3.5\)
意思是：掷很多次骰子，平均点数是 \(3.5\)。
线性性
线性性是期望最重要的性质之一：
\(\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\)
\(\mathbb{E}[aX + bY] = a\mathbb{E}[X] + b\mathbb{E}[Y]\)
这个性质不需要随机变量独立，在算法分析中非常有用。
例：两次掷骰子，求总点数期望
第一次为 \(X\)，第二次为 \(Y\)：
\(\mathbb{E}[X] = 3.5, \quad \mathbb{E}[Y] = 3.5\)
总点数 \(S = X+Y\)：
\(\mathbb{E}[S] = \mathbb{E}[X] + \mathbb{E}[Y] = 3.5 + 3.5 = 7\)
无需枚举 \(36\) 种结果，直接得到答案。
指示变量
在算法题中，我们经常想知道某个事件发生的次数。
此时可以引入指示变量（Indicator Variable）：
\(I_A = \begin{cases}
1, & \text{事件 } A \text{ 发生} \\
0, & \text{事件 } A \text{ 不发生}
\end{cases}\)
它的期望就是事件发生的概率：
\(\mathbb{E}[I_A] = P(A)\)
例：随机打乱 1~n，求不动点的期望
定义 \(I_i\) 表示位置 \(i\) 是否是原来的数字。
每个点是不动点的概率就为：
\(P(I_i=1) = 1/n\)
所以每个点的期望就为：
\(\mathbb{E}[I_i] = 1/n\)
不动点总数 \(X = \sum_{i=1}^n I_i\)：
\(\mathbb{E}[X] = \mathbb{E}[\sum_{i=1}^n I_i]\)
由线性性\(\mathbb{E}[aX] = a\mathbb{E}[X]\)可得：
\(\mathbb{E}[\sum_{i=1}^n I_i] = \sum_{i=1}^n \mathbb{E}[I_i] = n \times \frac{1}{n} = 1\)
所以不管 \(n\) 多大，期望总是不动点 \(= 1\)。
模运算与逆元
在算法题中，数学期望往往是一个分数，比如：
\(\mathbb{E} = \frac{P}{Q}\)
其中 \(P\) 和 \(Q\) 都是整数。
然而，如果题目要求对答案取模（比如常见的模数 \(998244353\)），我们不能直接做除法，因为 模运算中没有直接的「除」。
1. 除法转为乘法
在模意义下：
\(\frac{P}{Q} \equiv P \times Q^{-1} \pmod{MOD}\)
其中：
- \(Q^{-1}\) 称为 \(Q\) 的乘法逆元
- 它满足：
\(Q \times Q^{-1} \equiv 1 \pmod{MOD}\)
例子
假设 \(MOD=7\)，\(Q=3\)，那么
找到 \(Q^{-1}\)：
- \(3\times5=15\equiv 1 \ (\text{mod}\ 7)\)
所以 \(3^{-1} \equiv 5\)（模 \(7\) 下的逆元是 \(5\)）
那么：
\(\frac{4}{3} \equiv 4\times 5 \equiv 20 \equiv 6 \pmod{7}\)
2. 如何求逆元？
当 模数 \(MOD\) 是质数 时，可以用 费马小定理：
\(a^{MOD-1} \equiv 1 \ (\text{mod}\ MOD)\)
两边同时除以 \(a\)：
\(a^{MOD-2} \equiv a^{-1} \ (\text{mod}\ MOD)\)
于是：
\(Q^{-1} \equiv Q^{MOD-2} \pmod{MOD}\)
这意味着：只要我们能快速求幂，就能求出逆元。
3. 快速幂求逆元代码
ll qmi(ll a, ll b, ll p)
{
ll ans = 1 % p;
while (b)
{
if (b & 1)
ans = ans * a % p;
b >>= 1;
a = a * a % p;
}
return ans;
}
ll inv(ll q, ll mod)
{
return qmi(q, mod - 2, mod);
}题目讲解
题目链接：https://codeforces.com/contest/2008/problem/F
题目简述：
有一个盒子里有 \(n\) 个球，每个球上写着一个整数 \(a_i\)。朋友随机从盒子中 取两个不同的球（数值可能相同），记下它们的乘积。我们要求 所有可能的乘积的数学期望，并在 \(10^9+7\) 取模输出结果。
思路：
随机变量定义
设 \(X\) 表示随机取两个球（不放回）后，它们的数值乘积。
那么：
- \(x_i\) = 某一种可能出现的乘积值
- \(p_i\) = 这种乘积出现的概率
我们要算的就是：
\(\mathbb{E}[X] = \sum_{\text{所有可能的乘积}} (\text{乘积值}) \times (\text{出现概率})\)
出现概率 pi
从 \(n\) 个球中取两球的总方法数：
\({n \choose 2} = \frac{n(n-1)}{2}\)
如果我们考虑某对下标 \((u, v)\)，它被取到的概率是：
\(p_{u,v} = \frac{1}{n \choose 2}\)
展开期望公式
直接枚举所有二元组 \((u,v), u<v\)：
\(\mathbb{E}[X] = \sum_{1 \le u < v \le n} (a_u \cdot a_v) \cdot \frac{1}{n \choose 2}\)
也就是：
\(\mathbb{E}[X] = \frac{\sum_{1 \le u < v \le n} a_u \cdot a_v}{n \choose 2}\)
化简求和部分
已知：
\(\left(\sum_{i=1}^n a_i\right)^2 = \sum_{i=1}^n a_i^2 + 2\sum_{1 \le u < v \le n} a_u a_v\)
所以：
\(\sum_{1 \le u < v \le n} a_u a_v = \frac{\left(\sum_{i=1}^n a_i\right)^2 – \sum_{i=1}^n a_i^2}{2}\)
代回期望公式
\(\mathbb{E}[X] = \frac{\frac{\left(\sum a_i\right)^2 – \sum a_i^2}{2}}{{n}\choose{2}} = \frac{\left(\sum a_i\right)^2 – \sum a_i^2}{n(n-1)}\)
这就是 \(\mathbb{E}[X] = P / Q\) 的形式，其中：
- \(P = \left(\sum a_i\right)^2 – \sum a_i^2\)
- \(Q = n(n-1)\)
模运算部分
题目要求输出：
\(P \cdot Q^{-1} \bmod (10^9+7)\)
当模数是质数时，乘法逆元可以用费马小定理求：
\(Q^{-1} \equiv Q^{\text{MOD}-2} \pmod{\text{MOD}}\)
用快速幂 \(qmi(Q, MOD – 2, MOD)\) 就能求出来。
解决代码
ll qmi(ll a, ll b, ll p)
{
ll ans = 1 % p;
while (b)
{
if (b & 1)
ans = ans * a % p;
b >>= 1;
a = a * a % p;
}
return ans;
}
ll inv(ll q, ll mod)
{
return qmi(q, mod - 2, mod);
}
void solve()
{
ll n;
cin >> n;
ll sum1 = 0, sum2 = 0;
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
sum1 = (sum1 + x) % MOD;
sum2 = (sum2 + x * x % MOD) % MOD;
}
sum1 = sum1 * sum1 % MOD;
ll sum = (sum1 - sum2 + MOD) % MOD;
sum = sum * inv(2, MOD) % MOD;
ll cnt = n * (n - 1) / 2 % MOD;
cout << sum * inv(cnt, MOD) % MOD << endl;
}
