嵌套循环 C++ 的优化

Question

精通循环的人能否说明如何优化此任务 - 至少优化一点？也许一些缓存？或循环联合国切换？内存限制 512 m

#include <iostream>
using namespace std;

const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    int x = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            for (int k = i; k <= j; ++k) {
                x = (x + 1) % MOD;
            }
        }
    }
    cout << x << endl;
}

感谢任何帮助

Answer 1

一个简单的 WolframAlpha query 为您计算的循环提供了一个封闭形式的表达式：

x = (1/6 * n * (n + 1) * (n + 2)) % MOD

^{^{请在 Whosebug 上给我们 MathJax 支持！}}

然后，只需将封闭式表达式转换为代码即可。因为我们不希望x溢出，所以必须偶尔在运算结束前进行取模：

long long x = n % MOD;
x = (x * (n + 1)) % MOD;
x = (x * (n + 2) / 6) % MOD;

有了这个，数学运算的数量与n的大小无关，而且肯定比你的循环快得多。

嵌套循环 C++ 的优化

optimization for nested loop c++

c++

loops

nested-loops

compiler-optimization