F. 樱子的盒子 - 详细题解

问题重述

给定一个包含 $n$ 个整数的数组 $a$，从中随机选取两个不同的元素（无序），求这两个元素乘积的期望值。

期望值表示为 $\frac{P}{Q}$，需要输出 $P \cdot Q^{-1} \pmod{10^9+7}$。

---

数学推导

期望值的定义

从 $n$ 个元素中任选两个不同元素，总共有 $\binom{n}{2} = \frac{n(n-1)}{2}$ 种等可能的选择。

期望值为：

$$E = \frac{\sum_{1 \le i < j \le n} a_i \cdot a_j}{\binom{n}{2}} = \frac{\sum_{1 \le i < j \le n} a_i \cdot a_j}{\frac{n(n-1)}{2}} $$

---

分子化简

设总和为：

$$S = \sum_{i=1}^{n} a_i$$

平方和为：

$$Q = \sum_{i=1}^{n} a_i^2$$

考虑 $(S)^2$ 的展开：

$$S^2 = \left(\sum_{i=1}^{n} a_i\right)^2 = \sum_{i=1}^{n} a_i^2 + 2\sum_{1 \le i < j \le n} a_i a_j = Q + 2\sum_{1 \le i < j \le n} a_i a_j $$

因此：

$$\sum_{1 \le i < j \le n} a_i a_j = \frac{S^2 - Q}{2} $$

---

期望值公式

将分子代入期望值公式：

$$E = \frac{\frac{S^2 - Q}{2}}{\frac{n(n-1)}{2}} = \frac{S^2 - Q}{n(n-1)} $$

---

模运算处理

由于需要在模 $10^9+7$ 下输出结果，且模数是质数，可以使用费马小定理求逆元。

设模数 $p = 10^9+7$，则：

$$\text{答案} = (S^2 - Q) \cdot \text{inv}(n(n-1)) \pmod{p} $$

其中 $\text{inv}(x)$ 表示 $x$ 在模 $p$ 下的乘法逆元。

---

算法步骤

1. 读入 $n$ 和数组 $a$
2. 计算总和 $S = \sum a_i \bmod p$
3. 计算平方和 $Q = \sum a_i^2 \bmod p$
4. 计算分子 $M = (S^2 - Q + p) \bmod p$
5. 计算分母 $D = n(n-1) \bmod p$
6. 输出 $M \cdot \text{inv}(D) \bmod p$

---

快速幂求逆元

由于 $p$ 是质数，根据费马小定理：

$$x^{-1} \equiv x^{p-2} \pmod{p}$$

使用快速幂计算 $x^{p-2} \bmod p$。

---

完整代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;

// 快速幂
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        long long sum = 0, sum_sq = 0;
        
        for (int i = 0; i < n; i++) {
            long long x;
            cin >> x;
            sum = (sum + x) % mod;
            sum_sq = (sum_sq + x * x) % mod;
        }
        
        // 分子: S^2 - Q
        long long numerator = (sum * sum - sum_sq) % mod;
        numerator = (numerator + mod) % mod;
        
        // 分母: n(n-1)
        long long denominator = (1LL * n * (n - 1)) % mod;
        
        // 答案 = 分子 * 分母的逆元 mod p
        long long ans = numerator * binpow(denominator, mod - 2) % mod;
        
        cout << ans << "\n";
    }
    
    return 0;
}

---

时间复杂度

• 每个测试用例：$O(n)$
• 快速幂：$O(\log p)$
• 总复杂度：$O(\sum n) \le 2 \times 10^5$

---

示例验证

测试用例 1

$n = 3, a = [3, 2, 3]$

• $S = 3 + 2 + 3 = 8$
• $Q = 9 + 4 + 9 = 22$
• $S^2 - Q = 64 - 22 = 42$
• $n(n-1) = 3 \times 2 = 6$
• $E = 42 / 6 = 7$
• 输出：$7$

测试用例 2

$n = 4, a = [2, 2, 2, 4]$

• $S = 2 + 2 + 2 + 4 = 10$
• $Q = 4 + 4 + 4 + 16 = 28$
• $S^2 - Q = 100 - 28 = 72$
• $n(n-1) = 4 \times 3 = 12$
• $E = 72 / 12 = 6$
• 输出：$6$

测试用例 3

$n = 5, a = [1, 2, 3, 4, 5]$

• $S = 15$
• $Q = 1 + 4 + 9 + 16 + 25 = 55$
• $S^2 - Q = 225 - 55 = 170$
• $n(n-1) = 5 \times 4 = 20$
• $E = 170 / 20 = 8.5 = \frac{17}{2}$
• $17 \times 2^{-1} \bmod (10^9+7) = 17 \times 500000004 \bmod p = 500000012$

与样例输出完全一致。

---

关键公式总结

$$\boxed{E = \frac{(\sum a_i)^2 - \sum a_i^2}{n(n-1)}} $$

在模 $p$ 下计算时：

$$\text{ans} = \left((\sum a_i)^2 - \sum a_i^2\right) \cdot (n(n-1))^{p-2} \pmod{p} $$