能量波强度总和计算代码优化：从 TLE 到高效求解

### 🔍 问题分析 当前代码在计算第二部分时，使用了两层嵌套循环，时间复杂度为 $O(n^2)$，这会导致在处理大规模数据（如 $N = 5000005$）时超时。我们需要进一步优化这部分的计算，将其复杂度降低到 $O(n)$。 ### 💡 优化思路 对于 $\sum_{k = 3}^{n}a[k]\sum_{j = 1}^{k - 1}\sum_{i = 1}^{j - 1}a[i]$ 这部分，我们可以通过提前计算 $\sum_{j = 1}^{k - 1}\sum_{i = 1}^{j - 1}a[i]$ 的值，避免使用嵌套循环。 设 $s[j]=\sum_{i = 1}^{j - 1}a[i]$，那么 $\sum_{j = 1}^{k - 1}\sum_{i = 1}^{j - 1}a[i]=\sum_{j = 1}^{k - 1}s[j]$。我们可以在一次遍历中计算出 $s[j]$ 和 $\sum_{j = 1}^{k - 1}s[j]$ 的值。 ### 💻 优化后的代码 ```cpp #include <iostream> const int N = 5000005; const int MOD = 1000000007; typedef long long ll; ll a[N]; ll pre_sum[N]; // 前缀和数组 ll s[N]; // s[j] = sum(a[1]...a[j - 1]) ll s_sum[N]; // s_sum[k] = sum(s[1]...s[k - 1]) int main() { int n; std::cin >> n; // 读取能量波强度并计算前缀和 for (int i = 1; i <= n; ++i) { std::cin >> a[i]; pre_sum[i] = (pre_sum[i - 1] + a[i]) % MOD; } ll ans = 0; // 计算第一部分 for (int j = 2; j <= n; ++j) { ll term1 = (a[j] * pre_sum[j - 1] % MOD) * (n - j) % MOD; ans = (ans + term1) % MOD; } // 计算 s[j] 和 s_sum[k] for (int j = 1; j <= n; ++j) { s[j] = pre_sum[j - 1]; s_sum[j] = (s_sum[j - 1] + s[j]) % MOD; } // 计算第二部分 for (int k = 3; k <= n; ++k) { ll term2 = (a[k] * s_sum[k - 1]) % MOD; ans = (ans + term2) % MOD; } std::cout << ans << std::endl; return 0; } ``` ### 📈 复杂度分析 - **时间复杂度**：$O(n)$，通过预处理 $s[j]$ 和 $s\_sum[k]$，避免了嵌套循环，将复杂度降低到线性。 - **空间复杂度**：$O(n)$，主要用于存储前缀和数组、$s$ 数组和 $s\_sum$ 数组。 ######[AI问答 | 803点数解答 | 2026-05-31 19:27:19]