F. Sakurako's Box - 题解

比赛与标签

比赛: Codeforces Round 970 (Div. 3) 标签: combinatorics, math, number theory 难度: *1400

题目大意喵~

你好呀，未来的算法大师！Sakurako酱有一个装着 n 个小球的盒子，每个球上都有一个数值 a_i 呢。她想和朋友玩一个游戏：从盒子里随机拿出两个不同的小球，把它们的数值乘起来。

Sakurako酱想知道，这个乘积的期望值是多少。期望值可以表示成一个分数 P/Q，而题目要求我们输出 P * Q⁻¹ (mod 10⁹ + 7) 的结果。

简单来说，就是我们要计算从 n 个数中任选两个数，其乘积的平均值是多少，然后对一个大质数取模，喵~

输入:

• t 组测试数据。
• 每组数据第一行是一个整数 n，代表小球的数量。
• 第二行是 n 个整数 a_1, a_2, ..., a_n，代表每个小球的数值。

输出:

• 对于每组数据，输出一个整数，即乘积的期望值在模 10⁹ + 7 下的结果。

解题思路，一起动动脑筋吧！

看到“期望值”，有些同学可能会有点害怕，但别担心，让本喵来把它变简单~

期望值的基本公式是：E = (所有可能结果的总和) / (可能结果的总数)。

1. 可能结果的总数 (分母 Q)

我们要在 n 个小球中选出两个不同的小球。这是一个经典的组合问题，对吧？从 n 个元素中选2个，一共有 C(n, 2) 种选法。 C(n, 2) = n * (n - 1) / 2 这就是我们期望值公式里的分母部分啦！

2. 所有可能结果的总和 (分子 P)

这部分是关键！我们需要计算所有不同小球对 (a_i, a_j)（其中 i < j）的乘积之和。 也就是计算：Sum = a₁*a₂ + a₁*a₃ + ... + a₁*aₙ + a₂*a₃ + ... + a_{n-1}*aₙ

如果用两个 for 循环来暴力计算这个和，一个 i 从 1 到 n，一个 j 从 i+1 到 n，时间复杂度会是 O(n²)。但是题目中 n 最大有 2*10⁵，O(n²) 肯定会超时的说！( T﹏T )

所以，我们需要一个更聪明的办法，喵~ 这时候，一个神奇的数学恒等式就要登场啦！

考虑所有元素的和的平方： (a₁ + a₂ + ... + aₙ)²

把它展开会得到什么呢？ (a₁ + a₂ + ... + aₙ)² = (a₁² + a₂² + ... + aₙ²) + 2 * (a₁*a₂ + a₁*a₃ + ... + a_{n-1}*aₙ)

看呐！展开后的式子包含两部分：

1. 所有元素的平方和：Σ(a_i²)
2. 我们想要计算的所有不同对乘积之和，并且是两倍：2 * Sum

令 S_total = a₁ + a₂ + ... + aₙ（所有元素之和）。 令 S_square = a₁² + a₂² + ... + aₙ²（所有元素平方之和）。

那么上面的恒等式可以写成： S_total² = S_square + 2 * Sum

稍微移动一下，我们就能得到 Sum 的表达式啦！ Sum = (S_total² - S_square) / 2

这个 Sum 就是我们期望值公式里的分子！S_total 和 S_square 只需要一次 O(n) 的遍历就可以求出来，太棒了！

3. 整合起来！

现在我们把分子和分母放在一起，看看期望值 E 是什么： E = P / Q = Sum / C(n, 2)E = [ (S_total² - S_square) / 2 ] / [ n * (n - 1) / 2 ]

看，分子和分母里的 / 2 正好可以消掉！真是太巧了，喵~ E = (S_total² - S_square) / (n * (n - 1))

4. 模运算时间！

题目要求我们输出 P * Q⁻¹ (mod 10⁹ + 7)。 根据我们推导出的公式：

• P_mod = (S_total² - S_square) % mod
• Q_mod = (n * (n - 1)) % mod

因为 10⁹ + 7 是一个质数，所以求 Q_mod 的逆元 Q_mod⁻¹ 就可以用费马小定理啦！ Q_mod⁻¹ ≡ Q_mod ^ (mod - 2) (mod mod)

所以最终的答案就是： Ans = (P_mod * Q_mod⁻¹) % mod

总结一下我们的算法步骤:

1. 遍历一次数组 a，计算出 S_total = Σa_i 和 S_square = Σa_i²。记得每一步都取模哦！
2. 计算分子 P_mod = (S_total * S_total - S_square) % mod。注意，减法可能会出现负数，所以最好写成 (S_total*S_total - S_square + mod) % mod，这样就万无一失啦。
3. 计算分母 Q_mod = (n * (n - 1)) % mod。
4. 用快速幂计算 Q_mod 的逆元 inv_Q = Q_mod ^ (mod - 2) % mod。
5. 最终答案就是 (P_mod * inv_Q) % mod。

这样，我们就在 O(n) 的时间里解决了问题，是不是很高效呀？

代码实现喵~

#include <iostream>
#include <vector>
using namespace std;

// 定义模数，是个好习惯喵~
const long long mod = 1000000007;

// 快速幂模板，用来求逆元，非常重要！
long long pow_mod(long long base, long long exp, long long mod) {
    base %= mod;
    long long res = 1;
    while (exp > 0) {
        if (exp & 1) { // 如果指数是奇数
            res = (res * base) % mod;
        }
        base = (base * base) % mod; // 底数平方
        exp >>= 1; // 指数除以2
    }
    return res;
}

int main() {
    // 加速输入输出，让程序跑得飞快~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        
        long long total_mod = 0;      // 对应我们推导的 S_total
        long long sq_total_mod = 0;   // 对应我们推导的 S_square

        // 一次遍历，同时计算元素和与平方和
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            total_mod = (total_mod + a[i]) % mod;
            sq_total_mod = (sq_total_mod + (a[i] * a[i]) % mod) % mod;
        }

        // 计算 S_total^2
        long long T = (total_mod * total_mod) % mod;
        
        // 计算期望值的分子 P = S_total^2 - S_square
        // 加上 mod 是为了防止 T < sq_total_mod 时结果为负数
        long long numerator_mod = (T - sq_total_mod + mod) % mod;
        
        // 计算期望值的分母 Q = n * (n - 1)
        long long denom = (long long)n * (n - 1) % mod;
        
        // 用费马小定理求分母的逆元
        long long inv_denom = pow_mod(denom, mod - 2, mod);
        
        // 最终答案 = P * Q^-1 (mod mod)
        long long ans = numerator_mod * inv_denom % mod;
        
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(n) 的说。对于每组测试数据，我们只用了一个循环来遍历数组，时间复杂度是 O(n)。快速幂求逆元的时间复杂度是 O(log mod)。所以总的时间复杂度是 O(n + log mod)，由 O(n) 主导。所有测试数据的总和 Σn 不超过 2*10⁵，所以完全没问题！
• 空间复杂度: O(n) 的说。我们用了一个 vector 来存储输入的 n 个数，所以空间复杂度是 O(n)。

知识点与总结，喵~

这道题真是一道非常好的数学思维练习题呢！让我们来总结一下学到了什么吧：

1. 期望值计算: 期望值的核心是 总和 / 总数。遇到期望值问题，先分别思考如何计算分子和分母。
2. 平方和的恒等式: (Σa_i)² = Σ(a_i²) + 2 * Σ_{i<j}(a_i*a_j) 这个公式是解决本题的关键！它能巧妙地将 O(n²) 的配对求和问题转化为 O(n) 的问题，是组合数学中非常有用的技巧，一定要记住哦！
3. 模运算: 在算法竞赛中，当结果可能很大时，通常会要求对一个大质数取模。
   • 加、减、乘法都可以直接取模。
   • 减法要特别注意 (a - b + mod) % mod 防止出现负数。
   • 除法要转化为乘以模逆元。
4. 费马小定理: 当模数 p 是质数时，a^(p-2) 就是 a 在模 p 意义下的逆元。这是求逆元最常用的方法之一。

希望这篇题解能帮助你更好地理解这道题！继续加油，你一定能成为更厉害的算法大师的，喵~ (ฅ'ω'ฅ)