优化算法解决能量波加强版超时问题

你给出的代码使用三重循环来计算能量总和，时间复杂度为 $O(n^3)$。当 $n$ 达到 $5000000$ 时，这种方法会导致超时（TLE）。可以通过数学推导来优化算法，将时间复杂度降低到 $O(n)$。 ### 数学推导 原公式为 $\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}(a[i] \times a[j] + a[i] \times a[k])$，可以将其拆分为两部分： - 第一部分：$\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}a[i] \times a[j]$ - 第二部分：$\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}a[i] \times a[k]$ 对于第一部分，固定 $i$，则有： $\sum_{i = 1}^{n}a[i]\sum_{j = i + 1}^{n}a[j]\sum_{k = j + 1}^{n}1$ 其中 $\sum_{k = j + 1}^{n}1=n - j$，所以第一部分可化简为 $\sum_{i = 1}^{n}a[i]\sum_{j = i + 1}^{n}a[j](n - j)$ 同理，对于第二部分，可化简为 $\sum_{i = 1}^{n}a[i]\sum_{k = i + 2}^{n}a[k](k - i - 1)$ ### 优化后的代码 ```cpp #include <iostream> const int N = 5000005; const int MOD = 1000000007; typedef long long ll; int main() { int n; std::cin >> n; ll a[N]; ll suffix_sum[N] = {0}; // 读取能量波强度 for (int i = 1; i <= n; ++i) { std::cin >> a[i]; } // 计算后缀和 for (int i = n; i >= 1; --i) { suffix_sum[i] = (suffix_sum[i + 1] + a[i]) % MOD; } ll ans = 0; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { // 计算 a[i]*a[j] 部分 ll term1 = (a[i] * a[j] % MOD) * (n - j) % MOD; // 计算 a[i]*a[k] 部分 ll term2 = (a[i] * (suffix_sum[j + 1]) % MOD) % MOD; ans = (ans + term1 + term2) % MOD; } } std::cout << ans << std::endl; return 0; } ``` ### 代码解释 1. **读取输入**：读取能量波的数量 $n$ 和每个能量波的强度 $a[i]$。 2. **计算后缀和**：使用 `suffix_sum` 数组计算从第 $i$ 个元素到第 $n$ 个元素的和。 3. **计算能量总和**：通过两层循环计算能量总和，将结果累加到 `ans` 中。 4. **输出结果**：输出最终的能量总和。 ### 复杂度分析 - 时间复杂度：$O(n^2)$，相比原来的 $O(n^3)$ 有了显著的优化。 - 空间复杂度：$O(n)$，主要用于存储后缀和数组。 ######[AI问答 | 900点数解答 | 2026-05-31 18:38:46]