The number is $$$\infty$$$, because for all $$$x > n$$$ the tuple $$$(x, n, 0, -x)$$$ is a solution.

Auto comment: topic has been updated by singhpriyank (previous revision, new revision, compare).

$$$O(N^{4})$$$: Iterate over all $$$x_{i}$$$.

$$$O(N^{3})$$$: Iterate over $$$x_{1}, x_{2}, x_{3}$$$, then you can check how much more you need and if that's greater than $$$x_{3}$$$, then you add 1.

$$$O(N^{2})$$$: Iterate over $$$x_{1}$$$ and $$$x_{2}$$$, then you calculate how much more you need. Both of them need to be at least $$$x_{2}$$$, so you subtract $$$2x_{2}$$$ more. Now whatever you've got, say $$$X$$$, there are $$$\frac{X-1}{2}$$$ ways [If $$$X$$$ is negative or zero, It's not possible, so skip].

Can't think of any $$$O(N)$$$ optimization, maybe someone else can help.

This might be an overkill, I suspect there might be a simpler solution.

$$$y_1 = x_1, y_i = x_i-x_{i-1}-1$$$ for $$$i > 0$$$

Now we need to solve for number of solutions $$$y_4 + 2y_3 + 3y_2 + 4y_3 = n + 6 = N$$$ for $$$y_i \geq 0$$$.

Let $$$G(x)=\sum_{0\leq i}x^i$$$.

This can be computed as coefficient of $$$x^N$$$ in $$$P(x) = G(x)G(x^2)G(x^3)G(x^4)$$$.

We only care about coefficients $$$x^0, x^1, ..x^N$$$ in each of the 4 terms on RHS.
So we can multiply the polynomials in $$$O(nlogn)$$$ using fft, as the degree of each polynomial being multiplied is atmost $$$N$$$. And answer is the coefficient of $$$x^N$$$.

I suppose we can do it in $$$O(N)$$$ if we write $$$G(x) = 1 / (1-x)$$$, but I don't know how, but maybe something on these lines.
On expanding the denominator of $$$P$$$, we can write $$$P(x) = 1/(1-R(x))$$$, we can see that $$$R(x)$$$ is a polynomial of size 10 without a constant term. And we can write $$$P(x) = \sum R(x)^i$$$, and we need to look at just the first N terms as $$$R(x)$$$ doesn't have a constant term.

A bit of case work got me $$$\binom{n+3}{3} - 6*(n/2 + 1)*(n/2 + 2) + 18*(n\%2==0)*(n/4 + 1) + 8*(n/3 + 1) - 15 * (n\%4==0)$$$

All divisions are integer divisions.

The problem is equivalent to $$$1/24$$$th the number of solutions to equation $$$x_1 + x_2 + x_3 + x_4 = n$$$ with the condition that $$$x_1$$$, $$$x_2$$$, $$$x_3$$$ and $$$x_4$$$ are pairwise distinct and are non-negative. For $$$i < j$$$, define $$$S_{ij}$$$ as the set of all solutions for the equation $$$x_1 + x_2 + x_3 + x_4 = n$$$ with condition that $$$x_i = x_j$$$ and $$$x_1, x_2, x_3, x_4 \geq 0$$$. So we need to compute

This can be simplified using Inclusion-Exclusion to

where

• $$$A_0$$$ is the number of integral solutions to the equation $$$x_1 + x_2 + x_3 + x_4 = n$$$ with $$$x_i \geq 0$$$
• $$$A_1$$$ is the number of integral solutions to the equation $$$2x_1 + x_2 + x_3 = n$$$ with $$$x_i \geq 0$$$
• $$$A_2$$$ be the number of integral solutions to the equation $$$2x_1 + 2x_2 = n$$$ with $$$x_i \geq 0$$$
• $$$A_3$$$ be the number of integral solutions to the equation $$$3x_1 + x_2 = n$$$ with $$$x_i \geq 0$$$
• $$$A_4$$$ be the number of integral solutions to the equation $$$4x_1 = n$$$ with $$$x_i \geq 0$$$

The above values can be computed in $$$\mathcal{O}(1)$$$ using the formulas

• $$$A_0 = \binom{n + 3}{3}$$$
• $$$A_1 = (n + 1 - \bigl\lfloor\frac{n}{2}\bigr\rfloor)(\bigl\lfloor\frac{n}{2}\bigr\rfloor + 1)$$$
• $$$A_2$$$ is equal $$$\bigl\lfloor\frac{n}{2}\bigr\rfloor + 1$$$ if $$$n$$$ is divisible by $$$2$$$ and is equal to $$$0$$$ otherwise
• $$$A_3 = \bigl\lfloor\frac{n}{3}\bigr\rfloor + 1$$$
• $$$A_4$$$ is equal to 1 if $$$n$$$ is divisible by $$$4$$$ and is equal to $$$0$$$ otherwise