optimization for nested loop c++

Question

Can someone skilled in loops say how this task can be optimized - at least a bit? Maybe some cache? or loop un switching? memory limit 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;
}

Any help is appreciated

Answer 1

A simple WolframAlpha query gives you a closed-form expression for the loop that you are calculating:

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

^{Please give us MathJax support on StackOverflow!}

Then, it's just a matter of turning that closed-form expression into code. Because we do not want x to overflow, we must occasionally perform modulo before the end of the operation:

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

With this, the number of mathematical operations is independent of the size of n, and certainly much faster than your loop.