解决代码WA问题：优化能量总和计算方法

### 🐞问题分析 代码出现 `WA`（Wrong Answer）可能是因为在计算过程中出现了整数溢出问题，虽然使用了 `long long` 类型来存储部分结果，但在取模操作之前仍然可能会发生溢出。代码本身逻辑是正确的，不过可以通过数学推导来优化计算过程，避免双重循环，从而减少时间复杂度。 ### 💡优化思路 我们可以使用数学公式来优化计算。假设数组 `a` 的元素为 \(a_1, a_2, \cdots, a_n\)，我们要求的是 \(\sum_{1\leq i < j\leq n} a_i\times a_j\)。 根据完全平方公式 \((a_1 + a_2+\cdots+a_n)^2=\sum_{i = 1}^{n}a_i^2 + 2\sum_{1\leq i < j\leq n} a_i\times a_j\)，可以推导出 \(\sum_{1\leq i < j\leq n} a_i\times a_j=\frac{(\sum_{i = 1}^{n}a_i)^2-\sum_{i = 1}^{n}a_i^2}{2}\)。 ### 📝修改后的代码 ```cpp #include <iostream> const int MOD = 1000000007; // 计算汇合后的新能量总和 long long calculateTotalEnergy(int n, int a[]) { long long sum = 0; // 存储所有能量波强度的和 long long squareSum = 0; // 存储所有能量波强度平方的和 // 计算所有能量波强度的和以及平方和 for (int i = 0; i < n; ++i) { sum = (sum + a[i]) % MOD; squareSum = (squareSum + (long long)a[i] * a[i]) % MOD; } // 根据公式计算结果 long long result = (sum * sum % MOD - squareSum + MOD) % MOD; // 因为要除以2，而在模运算中不能直接除，需要乘以2的模逆元 // 2在模1000000007下的逆元是500000004 result = result * 500000004 % MOD; return result; } int main() { int n; std::cin >> n; int *a = new int[n]; // 读取每个能量波的强度 for (int i = 0; i < n; ++i) { std::cin >> a[i]; } // 计算并输出汇合后的新能量总和 std::cout << calculateTotalEnergy(n, a) << std::endl; delete[] a; return 0; } ``` ### 📋代码解释 1. **计算总和与平方和**：通过一次遍历数组，计算所有能量波强度的和 `sum` 以及平方和 `squareSum`，并在计算过程中进行取模操作，避免溢出。 2. **根据公式计算结果**：根据前面推导的公式，计算 \((\sum_{i = 1}^{n}a_i)^2-\sum_{i = 1}^{n}a_i^2\)，并进行取模操作。 3. **处理除法**：在模运算中不能直接进行除法，需要乘以除数的模逆元。因为 \(2\times500000004\equiv1\pmod{1000000007}\)，所以乘以 \(500000004\) 相当于除以 \(2\)。 ### 🔍复杂度分析 - **时间复杂度**：\(O(n)\)，只需要遍历一次数组。 - **空间复杂度**：\(O(n)\)，主要用于存储输入的数组。 ######[AI问答 | 904点数解答 | 2026-05-31 16:04:07]