优化算法：解决P3337能量波（加强版）计算问题

### 🔍 思路分析 原代码使用了三重循环来计算能量总和，时间复杂度为 $O(n^3)$，在 $n$ 较大时会超时。可以通过数学推导来优化，将原式 $\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}(a[i]*a[j]+a[i]*a[k])$ 进行化简。 先将式子拆分为两部分： 1. 对于 $\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}a[i]*a[j]$，可以先固定 $i$，再固定 $j$，$k$ 的取值范围是 $j + 1$ 到 $n$，那么 $\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}a[i]*a[j]=\sum_{i = 1}^{n}a[i]\sum_{j = i + 1}^{n}a[j]*(n - j)$。 2. 对于 $\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}a[i]*a[k]$，可以先固定 $i$，再固定 $j$，$k$ 的取值范围是 $j + 1$ 到 $n$，那么 $\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}a[i]*a[k]=\sum_{i = 1}^{n}a[i]\sum_{j = i + 1}^{n}\sum_{k = j + 1}^{n}a[k]$。 可以通过预处理后缀和来减少计算量，将时间复杂度优化到 $O(n)$。 ### 💻 代码实现 ```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; ans = (ans + term1 + term2) % MOD; } } std::cout << ans << std::endl; return 0; } ``` ### 📈 复杂度分析 - **时间复杂度**：$O(n)$，主要是预处理后缀和和计算结果的时间。 - **空间复杂度**：$O(n)$，主要是后缀和数组的空间。 ######[AI问答 | 839点数解答 | 2026-05-31 18:47:07]